Центральный Дом Знаний - Алгоритм Касаи

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Я учусь (закончил(-а) в
Всего ответов: 2688

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

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

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

Loading

Календарь

«  Март 2024  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
25262728293031

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24