Самый длинный общий префиксный массив

Question

Ниже приведена информация Suffix array и LCP array для строки MISSISSIPPI.Я знаю, что LCP дает информацию о длине самого длинного общего префикса между str[i - 1] и str[i].Как получить самую длинную длину общего префикса между любыми двумя произвольными суффиксами этой строки.Например, я хочу самый длинный общий префикс между MISSISSIPPI и ISSIPPI

SA  LCP
12  0     $
11  0     I$
8   1     IPPI$
5   1     ISSIPPI$
2   4     ISSISSIPPI$
1   0     MISSISSIPPI$
10  0     PI$
9   1     PPI$
7   0     SIPPI$
4   2     SISSIPPI$
6   1     SSIPPI$
3   3     SSISSIPPI$

Answer 1

Из http://en.wikipedia.org/wiki/Suffix_array, мы получаем, что «тот факт, что минимальное значение lcp, принадлежащее последовательному набору отсортированных суффиксов, дает самый длинный общий префикс среди всех этих суффиксов, также может быть полезен».Таким образом, в вашем случае, LCP между MISSISSIPPI и ISSIPPI равен min (4, 0) = 0.

Вы можете найти минимум в диапазоне во времени O (1) через http://en.wikipedia.org/wiki/Range_Minimum_Query, и таммного информации об альтернативных подходах, если вы посмотрите там ссылку TopCoder.