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

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

Реализация на языке 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]  } 

Примечания[править | править код]

Литература[править | править код]

• Kasai, Toru and Lee, Gunho and Arimura, Hiroki and Arikawa, Setsuo and Park, Kunsoo (2001). "Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications". Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching. CPM '01. Springer-Verlag. pp. 181--192. Kasai:2001:LLC:647820.736222. Дата обращения: 6 декабря 2013.{{cite conference}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
• Guigo, R. and Gusfield, D. Algorithms in Bioinformatics: Second International Workshop, WABI 2002, Rome, Italy, September 17-21, 2002, Proceedings. — Springer, 2002. — P. 453-455. — ISBN 9783540442110.

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (20 декабря 2014)

int main() {   printf("Hi");   return 0; }