Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

Z-algorithm詳解と具体例

新ABCになって、6問制になってから、2020/1/6現在まで、Z-algorithmは二回(500, 600)出題されてます。これからも継続して出そうな「文字列照合」で強力なツールとなるZ-algorithmですが、既存資料たちは非常によく説明されていますが、どこか筆足らずのような印象を受けました。
そこで、この記事でZ-algorithmに絞った説明、実際の挙動の説明、実装例を紹介します。

以下のページ、PDFを参考にしてます。

snuke.hatenablog.com

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の原理

f:id:Sen_comp:20200118001528j:plain

f:id:Sen_comp:20200118001601j:plain

f:id:Sen_comp:20200118001634j:plain

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の接頭辞を求めるというのがドンピシャの問題もあるため、これもできるとより強くなれると思います。