Алгоритм Касаи
Алгоритм
Касаи (Аримуры — Арикавы
— Касаи — Ли — Парка), алгоритм, за
линейное время находящий длины наибольших
общих префиксов (англ. lcp,
longest common prefix) у всех пар
суффиксов данной строки, соседних в
лексикографическом порядке (т.е. у всех
соседних элементов суффиксного
массива). Входом алгоритма являются
сама строка и суффиксный массив, выходом
— массив длин наибольших общих префиксов.
Реализация
алгоритма на языке Java:
public class Kasai {
// в sufArray (s.length() + 1) элементов — включая пустой суффикс
public static int[] solve(String s, String[] sufArray) {
int pos[] = new int[s.length() + 1];
for (int i = 0; i <= s.length(); i++) {
pos[i] = s.length() - sufArray[i].length() + 1;
}
int rank[] = new int[s.length() + 1];
for (int i = 0; i <= s.length(); i++) {
rank[pos[i]] = i;
}
int ans[] = new int[s.length() + 1];
int h = 0;
for (int i = 1; i <= s.length(); i++) {
if (rank[i] > 1) {
int k = pos[rank[i] - 1];
while (((i + h - 1) != s.length())
&& ((k + h - 1) != s.length())
&& (s.charAt(i + h - 1) == s.charAt(k + h - 1)))
h++;
ans[rank[i]] = h;
if (h > 0)
h--;
}
}
return ans; // ans[i + 1] = длина наибольшего общего префикса sufArray[i] и sufArray[i - 1]