Zアルゴリズム

目的

文字列Sに対して、SとS.substring[i,S.length)の共通prefix長を、各i=0,1,...,S.length-1に対して計算します。

計算量

$O(S.length)$

使い方

int[] zalgo(String S)
i番目にSとS.substring[i,S.length)の共通prefix長を保存した配列をreturnします。

参考文献

http://snuke.hatenablog.com/entry/2014/12/03/214243

ソースコード

int[] zalgo(String s) {
	int n = s.length();
	int[] ret = new int[n];
	ret[0] = n;
	int i = 1, j = 0;
	while (i < n) {
		while (i + j < n && s.charAt(j) == s.charAt(i + j))
			++j;
		ret[i] = j;
		if (j == 0) {
			++i;
			continue;
		}
		int k = 1;
		while (i + k < n && k + ret[k] < j) {
			ret[i + k] = ret[k];
			++k;
		}
		i += k;
		j -= k;
	}
	return ret;
}