Самая длинная повторяющаяся подстрока - лучшая сложность

Question

Я реализовал решение, сравнивая суффиксы строки после сортировки списка суффиксов. Есть ли алгоритм линейного времени, который работает лучше, чем этот кусок кода?

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
void preCompute(string input[],string s)
{
    int n = s.length();
    for(int i=0; i<n; i++)
        input[i] = s.substr(i,n);
}
string LongestCommonSubString(string first,string second)
{
    int n = min(first.length(),second.length());
    for(int i=0; i<n; i++)
        if(first[i]!=second[i])
            return first.substr(0,i);
    return first.substr(0,n);
}
string lrs(string s)
{
    int n = s.length();
    string input[n];
    preCompute(input,s);
    sort(input, input+n);
    string lrs = "";
    for(int i=0; i<n-1; i++)
    {
        string x = LongestCommonSubString(input[i],input[i+1]);
        if(x.length()>lrs.length())
        {
            lrs = x;
        }
    }
    return lrs;
}
int main()
{
    string input[2] = {"banana","missisipi"};
    for(int i=0;i<2;i++)
        cout<<lrs(input[i])<<endl;
    return 0;
}

Я нашел действительно хороший ресурс для этого вопроса. Смотри здесь

Answer 1

Вы можете построить дерево суффиксов за линейное время (см. this ). Самая длинная повторяющаяся подстрока соответствует самому глубокому внутреннему узлу (когда я говорю «самый глубокий», я имею в виду, что путь от корня имеет максимальное количество символов, а не максимальное количество ребер). Причина этого проста. Внутренние узлы соответствуют префиксам суффиксов (то есть подстрок), которые встречаются в нескольких суффиксах.

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

1. Не создавать подстроки, подстроки могут быть обозначены парой чисел. Когда вам нужны настоящие символы, найдите оригинальную строку. Фактически суффиксы соответствуют одному индексу (начальному индексу).

2. Самый длинный общий префикс из каждой пары последовательных суффиксов можно вычислить при построении массива суффиксов за линейное время (но алгоритмы O (n log n) намного проще). Обратитесь к ссылкам это .

3. Если вы действительно настаиваете на том, чтобы все выполнялось за линейное время, то вы можете построить массив суффиксов за линейное время. Я уверен, что если немного поискать, вы легко найдете указатели.

4. Существуют очень элегантные (но не линейные) реализации, описанные здесь .