Реализации алгоритмов/Линеаризация циклической строки
Необходимо разрезать циклическую подстроку так, чтобы полученная линейная строка была лексикографически наименьшей среди всех возможных разрезов.
C++[править]
std::string TSuffixTree::LexMinString(const size_t & n) {
return LexMinString(0, n);
}
std::string TSuffixTree::LexMinString(const int id, const size_t & n) {
char lexMinId = 0;
for (size_t i = 0; i < Data[id].size(); ++i) {
if (DataString[Data[id][i].Left] < DataString[Data[id][lexMinId].Left]) {
lexMinId = i;
}
}
size_t curEdgeLen = *Data[id][lexMinId].Right - Data[id][lexMinId].Left;
if (n <= curEdgeLen) {
return DataString.substr(Data[id][lexMinId].Left, n);
} else {
std::string res = DataString.substr(Data[id][lexMinId].Left, curEdgeLen);
return res + LexMinString(Data[id][lexMinId].IdTo, n - curEdgeLen);
}
}