- Алгоритм Касаи
-
Алгоритм Касаи (Аримуры — Арикавы — Касаи — Ли — Парка) — алгоритм, за линейное время находящий длины наибольших общих префиксов (англ. 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] } }
Категория:- Алгоритмы
Wikimedia Foundation. 2010.