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

Алгоритм Касаи (Аримуры — Арикавы — Касаи — Ли — Парка) — алгоритм, за линейное время находящий длины наибольших общих префиксов (англ. 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). "[dl.acm.org/citation.cfm?id=647820.736222 Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications]" in CPM '01. Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching: 181--192, Springer-Verlag. Kasai:2001:LLC:647820.736222. Проверено 2013-12-06. 
• 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.

К:Википедия:Статьи без источников (тип: не указан)

Отрывок, характеризующий Алгоритм Касаи

– Вы про левый фланг? – сказал Кайсаров.
– Да, да, именно. Левый фланг наш теперь очень, очень силен.
Несмотря на то, что Кутузов выгонял всех лишних из штаба, Борис после перемен, произведенных Кутузовым, сумел удержаться при главной квартире. Борис пристроился к графу Бенигсену. Граф Бенигсен, как и все люди, при которых находился Борис, считал молодого князя Друбецкого неоцененным человеком.
В начальствовании армией были две резкие, определенные партии: партия Кутузова и партия Бенигсена, начальника штаба. Борис находился при этой последней партии, и никто так, как он, не умел, воздавая раболепное уважение Кутузову, давать чувствовать, что старик плох и что все дело ведется Бенигсеном. Теперь наступила решительная минута сражения, которая должна была или уничтожить Кутузова и передать власть Бенигсену, или, ежели бы даже Кутузов выиграл сражение, дать почувствовать, что все сделано Бенигсеном. Во всяком случае, за завтрашний день должны были быть розданы большие награды и выдвинуты вперед новые люди. И вследствие этого Борис находился в раздраженном оживлении весь этот день.
За Кайсаровым к Пьеру еще подошли другие из его знакомых, и он не успевал отвечать на расспросы о Москве, которыми они засыпали его, и не успевал выслушивать рассказов, которые ему делали. На всех лицах выражались оживление и тревога. Но Пьеру казалось, что причина возбуждения, выражавшегося на некоторых из этих лиц, лежала больше в вопросах личного успеха, и у него не выходило из головы то другое выражение возбуждения, которое он видел на других лицах и которое говорило о вопросах не личных, а общих, вопросах жизни и смерти. Кутузов заметил фигуру Пьера и группу, собравшуюся около него.
– Позовите его ко мне, – сказал Кутузов. Адъютант передал желание светлейшего, и Пьер направился к скамейке. Но еще прежде него к Кутузову подошел рядовой ополченец. Это был Долохов.
– Этот как тут? – спросил Пьер.
– Это такая бестия, везде пролезет! – отвечали Пьеру. – Ведь он разжалован. Теперь ему выскочить надо. Какие то проекты подавал и в цепь неприятельскую ночью лазил… но молодец!..