Алгоритм Касаи (Аримуры — Арикавы — Касаи — Ли — Пака) — алгоритм, за линейное время находящий длины наибольших общих префиксов () у всех пар суффиксов данной строки, соседних в лексикографическом порядке (то есть у всех соседних элементов суффиксного массива). Входом алгоритма являются сама строка и суффиксный массив, выходом — массив длин наибольших общих префиксов.
Реализация алгоритма на языке 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]
Реализация на языке C++ // Эта реализация предполагает наличие в конце строки text символа, отличного от всех остальных ("терминальный символ"). // Обратите внимание, что реализация алгоритма заметно отличается от предыдущей.
void solve(const std::string& text, const std::vector<int>& pos, std::vector<int>& lcp) { int n = text.length(); std::vector<int> rank(n); for (int i = 0; i < n; ++i) rank[pos[i]] = i; for (int i = 0, k = 0; i < n; ++i) { if (k > 0) k--; if (rank[i] == n - 1)
lcp[n - 1] = -1, k = 0; continue;
int j = pos[rank[i] + 1]; while (max(i + k, j + k) < text.length() && text[i + k] == text[j + k]) k++; lcp[rank[i]] = k; } // lcp[x] - длина наибольшего общего префикса суффиксов pos[x] и pos[x + 1] }
Примечания
Литература
Категория:Алгоритмы