Я узнаю о массивах Суффикса и успешно изучил, как сделать массив Суффикса в O (nlognlogn) раз Из этого Tutorial.Выполнение LCP из массива суффикса
Теперь мне интересно Как я могу создать массив LCP из моего массива суффикса в O (nlogn) или лучше, я знаю подход O (n * n). Я хочу что-то Лучшее
Я не нашел хорошего онлайн-ресурса Пожалуйста, помогите мне, чтобы я мог полностью изучить эту тему, и это поможет другому.
Благодаря
Простейшим О (п) подход заключается в петле слева направо (самый длинный в самой короткой) суффикс. Затем обратите внимание, что если самый длинный общий префикс (LCP) между текущим суффиксом в i и его соседе в таблице отсортированных суффиксов равен h, следующий LCP в i + 1 может уменьшиться не более чем на один. Это связано с тем, что следующий суффикс эквивалентен продвижению первого символа на единицу, поэтому мы могли бы достичь h - 1, по крайней мере, только путем продвижения соседа на один символ. Если между ними будет происходить разный суффикс, он по-прежнему будет иметь префикс по крайней мере h - 1.
Это позволяет нам сделать алгоритм амортизации O (n), продвигаясь вперед по мере необходимости, а затем продвигаясь вперед назад при переходе к следующему индексу.
Correct (AFAIK) реализация: https://sites.google.com/site/indy256/algo/suffix_array
Вы можете сделать LCP массив из массива суффиксов в O (N) время, используя alorithm Касаи в
Прекрасного описания. Мне полезно подумать о временной сложности, например: Сначала предположим, что мы никогда не уменьшали LCP; то, очевидно, в течение всего алгоритма он мог бы продвигаться не более n раз (поскольку ни одна пара строк не может иметь LCP> n), для общей сложности O (n). Но на самом деле нам, возможно, придется уменьшить его на 1 для каждого суффикса, т. Е. До n раз, и каждое из этих уменьшений означает, что одно дополнительное увеличение возможно позже. Но тогда все еще не более n + n = 2n увеличивается, а n уменьшается, для O (3n) = O (n) шагов в целом. –
Извините, если я неправильно понял, что вы говорите, и я не смотрел ваш код, но вы, кажется, подразумеваете, что разница между двумя соседними элементами LCP никогда не превышает 1. Это, безусловно, неверно. – jogojapan
Извините за неудобную формулировку (английский язык не так прост, как C++), но это не так просто, как вы описали. Мы повторяем предварительные сортировки (от длинного до кратчайшего) и проверяем их LCP. Когда вы перебираете эти индексы (которые, вероятно, не являются последовательными в таблице массива суффикса), LCP может уменьшаться не более чем на один. Код в ссылке довольно короткий/ясный. –