Z-Algorithm

文字列 s に対して、各 i について

z[i] = s[i..] と s[0..] の最長共通接頭辞の長さ

を O(N) で求めるアルゴリズム。

何ができるか

各位置 i から始まる suffix が、prefix と何文字一致するかを求める
文字列検索
文字列の周期性の判定
prefix に関する条件判定

イメージ

例えば、

S = "ABACABABC"

のとき、Z 配列は次のようになる。

位置	0	1	2	3	4	5	6	7	8
文字	A	B	A	C	A	B	A	B	C
Z値	9	0	1	0	3	0	2	0	0

意味は次の通り。

z[0] = 9
文字列全体なので長さは 9
z[2] = 1
"ACABABC" と "ABACABABC" は先頭の "A" の1文字だけ一致
z[4] = 3
"ABABC" と "ABACABABC" は "ABA" の3文字一致
z[6] = 2
"ABC" と "ABACABABC" は "AB" の2文字一致

つまり、
「各 i から始まる文字列が、先頭とどれだけ一致しているか」を配列にしたものが Z 配列。

実装

cpp

#pragma once
#include <string>
#include <vector>
using namespace std;

// z[i] = s[i..] と s[0..] の最長共通接頭辞の長さ
// 特に z[0] = s.size()
vector<int> z_algorithm(const string& s) {
    int n = (int)s.size();
    vector<int> z(n);
    if (n == 0) return z;
    z[0] = n;
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}

使用例

cpp

string s = "ABACABABC";
auto z = z_algorithm(s);

// z = {9, 0, 1, 0, 3, 0, 2, 0, 0}

典型的な使い方

文字列検索

pattern = p, text = t として、

p + '#' + t

に対して Z-Algorithm を実行すると、 z[i] == p.size() となる位置が、p の出現位置に対応する。

周期性の判定

i + z[i] == n かつ n % i == 0 のような条件を見ることで、文字列の周期を判定できることがある。

注意点

z[0] を 0 にする流儀もあるが、この実装では z[0] = n としている。
空文字列なら空配列を返す。
KMP と似た用途で使えることがあるが、求めている配列の意味は異なる。
z[i] は「suffix の長さ」ではなく、「prefix との一致長」である。

計算量

O(N)

各文字をならして見ると、全体で線形時間になる。

Z-Algorithm ​

何ができるか ​

イメージ ​

実装 ​

使用例 ​

典型的な使い方 ​

文字列検索 ​

周期性の判定 ​

注意点 ​

計算量 ​

関連 ​