1 Тема от Sergey

  • Sergey
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-07-14
  • Сообщений: 8

Тема: Суффиксный массив

В разделе "Применение суффиксного массива. Наибольший общий префикс двух соседних суффиксов" есть предложение: "Первые половинки подстрок различались. Заметим, что тогда на предыдущем шаге эти первые половинки необходимо были соседними." Это не так. Если на предыдущем шаге было несколько одинаковых подстрок, то первые половинки могли и не быть соседними.
Пусть дана строка ABAB.
Тогда после первой фазы получим 4 подстроки из 2х символов:
AB
AB
BA
BA
На следующем шаге возможно сравнение первой и третьей (или первой и четвертой) подстрок, хотя они и не являются соседними.

2 Ответ от it4.kp

  • it4.kp
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-07-13
  • Сообщений: 15

Re: Суффиксный массив

Они являются соседними. На k-той итерации есть несколько "корзин". В каждой из них находятся суффиксы у которых первые k символов совпадают. Под соседством имеется ввиду соседство корзин. С каждой итерацией происходит уточнение этих корзин с учетом 2^k символов. Если две корзины соседние, то есть два варианта. Либо на предыдущей итерации они были одной корзиной и в результате уточнения распались, тогда у них суффиксов этих корзин первые половинки совпадают. Либо на предыдущей итерации они уже были разными корзинами, тогда эти разные корзины обязательно были соседними, потому что если бы это было не так, то на текущей итерации наши уточненные корзины уж тем более не были бы соседними...

3 Ответ от Sergey

  • Sergey
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-07-14
  • Сообщений: 8

Re: Суффиксный массив

Если в одной "корзине" лежит несколько одинаковых подстрок, то lcp для всех, кроме одной, равняется длине этих подстрок, а lcp оставшейся равен наибольшему общему префиксу от подстрок этой и следующей "корзины".
Когда на очередном этапе мы видим, что первые половинки новых подстрок на предыдущем этапе были в разных "корзинах", то lcp этих подстрок берем равным тому, что был на предыдущем шаге. Т.е. надо брать "старый" lcp между "корзинами".
В приведенной же реализации (http://e-maxx.ru/algo/suffix_array) берется "старый" lcp от одной из строк первой "корзины", но (как показано в первом абзаце) только для "последней" строки "корзины" мы получим верный ответ. Для всех остальных мы получаем длину всей строки. Проблема в том, что "последней" строки на данном этапе уже может не быть, вернее она перестанет быть "последней".