Z algorithm

ここを読んで勉強した。
コメント読むとKMPと等価とか書かれているけどよく分からない。とりあえずパターンマッチングのO(M+N)が使えるのは良い。
原理の解説も元記事にあるけど、とりあえず入力とパターンマッチングへの応用法だけ書いておく。
長さLの文字列strに対して、整数列Zを構成する。Z[i]={str[i]から始まる、strのprefixになっている部分文字列の最長の長さ}である。計算量O(L)。
長さMの文字列Tを長さNの文字列Sの中から探したいときは、T ++ # ++ Sという長さM+1+Nの文字列(#はダミー文字)に対してZ algorithmを適用する。このとき、Z[i]の値がMになっているところを探せば良い。

char str[MAX_L + 1];
int Z[MAX_L];

//Z[0]には0が入っている。これは適当にいじってもよい(以下のコードに影響はない)。
void z_algorithm(){
	const int L = strlen(str);

	for(int i=1, left=0, right=0; i<L; i++){
		if(i > right){
			left = right = i;
			for(;right < L && str[right-left] == str[right]; right++);
			Z[i] = right - left;
			right--;
		}
		else{
			int k = i - left;
			if(Z[k] < right - i + 1){
				Z[i] = Z[k];
			}
			else{
				left = i;
				for(;right < L && str[right-left] == str[right]; right++);
				Z[i] = right - left;
				right--;
			}
		}
	}
}