Z-algorithm詳解と具体例
新ABCになって、6問制になってから、2020/1/6現在まで、Z-algorithmは二回(500, 600)出題されてます。これからも継続して出そうな「文字列照合」で強力なツールとなるZ-algorithmですが、既存資料たちは非常によく説明されていますが、どこか筆足らずのような印象を受けました。
そこで、この記事でZ-algorithmに絞った説明、実際の挙動の説明、実装例を紹介します。
以下のページ、PDFを参考にしてます。
www.slideshare.net
Z-algorithmで何ができるか?
文字列Sに対して、S[i : j]という記号を、Sのi番目からj番目(いずれも0-idx)までの連続部分文字列とします。
例えば、S="abcde"で
- S[1 : 2] = "bc"
- S[3 : 3] = "d"
- S[0 : 4] = "abcde"
とそれぞれなります。
Z-algorithmは、文字列Sに対して、Sの長さを|S|とすると、「すべての0 <= i <= |S| - 1を満たすiについて、S[0, |S| - 1](つまりS全体)とS[i, |S| - 1]の一致する接頭辞の長さ(それぞれ最初から何文字まで一致するか)を、O(|S|)で計算できる」。
一方、単純な二重ループで上のようにすべてのiについて求めると、O(N^2)かかります。
Z-algorithmの原理
Z-algorithmの実装例
先ほどの画像の説明通りに、実装してみました。
vector<int> Z_algorithm(string S) { int c = 0, n = S.size(); //接頭辞の長さを保存する配列を返す。 //i = 1からやるとする。 //Z[1]には赤下線が存在しないので、「溢れるor共通部分がない」のところにまずいく。 //実装上、上のような挙動をしてもらうため、Z[0]=n;は[1, n - 1]まで計算が終わった後に入れる。 //cは、赤下線の左端の位置。 vector<int> Z(n, 0); for (int i = 1; i < n; i++) { int l = i - c; //今着目してる部分が赤下線の左端から何個分離れているかをlに入れる。 if (i + Z[l] < c + Z[c]) { //この条件を満たすのは、「青下線が赤下線に収まる」。 //この時、すでに計算されてるなのでそれを流用する。 Z[i] = Z[l]; } else { //この条件を満たすのは、「赤下線から青下線が溢れる」or「赤下線と青下線の共通部分がない」。 int j = max(0, c + Z[c] - i); //c + Z[c] - i > 0の時、これは「溢れる」が該当する。 //溢れてるのなら、収まる分は計算せずに、溢れた分(j番目から)だけ愚直に突き合わせればよい。 //そもそも共通部分がないならば、全部突き合わせる。この時、式からj = 0;となるとわかる。 //愚直に突き合せてる部分 while (i + j < n && S[j] == S[i + j])j++; Z[i] = j; //今の見てるiで、赤下線に完全に含まれなくなったので、今のiを赤下線の左端として、次のiをまた計算する。 c = i; } } //最後にこれを忘れずに Z[0] = n; return Z; }
具体例
ここで、Z-algorithmの計算例を1つ、理解を進めるために上げます。
S = "aabaaabaa"
i = 1
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
この時、c = 0。lはi - cなので、l = 1 - 0 = 1
i + Z[l] < c + Z[c]は、1 + 0 < 0 + 0なので、満たさない。下のelseへ。
愚直に計算すると、"abaaabaa"とSの接頭辞の長さは1。
よって、c=1と更新してZ[i]も更新する。
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
i = 2
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
この時、c = 1。lはi - cなので、l = 2 - 1 = 1
i + Z[l] < c + Z[c]は、2 + 1 < 1 + 1なので、満たさない。下のelseへ。
愚直に計算すると、"baaabaa"とSの接頭辞の長さは0。
よって、c=2と更新してZ[i]も更新する。
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
i = 3
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
この時、c = 2。lはi - cなので、l = 3 - 2 = 1
i + Z[l] < c + Z[c]は、3 + 1 < 2 + 0なので、満たさない。下のelseへ。
愚直に計算すると、"aaabaa"とSの接頭辞の長さは2。
よって、c=3と更新してZ[i]も更新する。
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 1 | 0 | 2 | 0 | 0 | 0 | 0 | 0 |
i = 4
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 1 | 0 | 2 | 0 | 0 | 0 | 0 | 0 |
この時、c = 3。lはi - cなので、l = 4 - 3 = 1
i + Z[l] < c + Z[c]は、4 + 1 < 3 + 2なので、満たさない。下のelseへ。
愚直に計算すると、"aabaa"とSの接頭辞の長さは5。
よって、c=4と更新してZ[i]も更新する。
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 1 | 0 | 2 | 5 | 0 | 0 | 0 | 0 |
i = 5
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 1 | 0 | 2 | 5 | 0 | 0 | 0 | 0 |
この時、c = 4。lはi - cなので、l = 5 - 4 = 1
i + Z[l] < c + Z[c]は、5 + 1 < 4 + 5なので、満たす。上のifへ。
Cはそのまま、Z[i]はすでに計算されてたZ[1]で更新する。
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 1 | 0 | 2 | 5 | 1 | 0 | 0 | 0 |
i = 6
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 1 | 0 | 2 | 5 | 1 | 0 | 0 | 0 |
この時、c = 4。lはi - cなので、l = 6 - 4 = 2
i + Z[l] < c + Z[c]は、6 + 0 < 4 + 5なので、満たす。上のifへ。
Cはそのまま、Z[i]はすでに計算されてたZ[2]で更新する。
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 1 | 0 | 2 | 5 | 1 | 0 | 0 | 0 |
i = 7
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 1 | 0 | 2 | 5 | 1 | 0 | 0 | 0 |
この時、c = 4。lはi - cなので、l = 7 - 4 = 3
i + Z[l] < c + Z[c]は、7 + 2 < 4 + 5なので、満たさない。下のelseへ。
愚直に計算すると、"aa"とSの接頭辞の長さは2。
よって、c=7と更新してZ[i]も更新する。
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 1 | 0 | 2 | 5 | 1 | 0 | 2 | 0 |
i = 8
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 1 | 0 | 2 | 5 | 1 | 0 | 2 | 0 |
この時、c = 7。lはi - cなので、l = 8 - 7 = 1
i + Z[l] < c + Z[c]は、8 + 1 < 7 + 2なので、満たさない。下のelseへ。
愚直に計算すると、"a"とSの接頭辞の長さは1。
よって、c=8と更新してZ[i]も更新する。
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 1 | 0 | 2 | 5 | 1 | 0 | 2 | 1 |
最後にZ[0]=9と更新して、終わり。
Z[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 1 | 0 | 2 | 5 | 1 | 0 | 2 | 1 |
実用例
例えば、文字列での一致検索では、次のように文字列を工夫させて使える。この考えの応用で、(https://atcoder.jp/contests/abc150/tasks/abc150_f:title=ABC150-F])が解ける。
string S, T;//Sの中にTはあるか?をO(|S| + |T|)で求める。 string tmp = S + T; int cnt = 0; vector<int> res = Z_algorithm(tmp); for(int i = S.size(); i < S.size() + T.size(); i++){ //最初のS.size()+1目からがTとなる。 //よって、これのZalgoのresが|S|以上ならば、tmpの最初の|S|文字を接頭辞として持つということなので //i - S.size()の場所でSが見つかってるということになる。 if(res[i] >= S.size())cnt++; }
最後に
文字列照合は応用手法の一つであり、ほかにKMP法、MP法、ローリングハッシュでも同じ計算量でできます。しかし、Z-algorithmの接頭辞を求めるというのがドンピシャの問題もあるため、これもできるとより強くなれると思います。