Реализации алгоритмов/Линеаризация циклической строки

Необходимо разрезать циклическую подстроку так, чтобы полученная линейная строка была лексикографически наименьшей среди всех возможных разрезов.

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);
    }
}

См. также

• Алгоритм Укконена.