Алгоритм Касаи

Алгоритм Касаи

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

Игры ⚽ Нужно решить контрольную?

Полезное


Смотреть что такое "Алгоритм Касаи" в других словарях:

  • Алгоритм касаи — алгоритм, который ищет самый длинный общий префикс из поданных на вход в лексиграфическом порядке массиве префиксов некоторой строки. (LCP Longest Common Prefix) Реализация алгоритма на языке Java. import java.io.*; import java.util.*; import… …   Википедия

  • Касаи (значения) — Касаи: Касаи  приток реки Конго, протекает по Центральной Африке. Горнорудное государство Южное Касаи сепаратистское государственное образование, существовавшее на территории Республики Конго в 1960 1962 годах. Касаи, Нориаки  известный …   Википедия

  • Суффиксный массив — Суффиксный массив  лексикографически отсортированный массив всех суффиксов строки. Эта структура данных была разработана Джином Майерсом и Уди Манбером как более экономная альтернатива суффиксному дереву с точки зрения необходимой памяти.… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»