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--; } } } }