最長共通接頭辞(Z-Algorithm)

説明

ある文字列 $S$ が与えられているとする。Z-Algorithm では, それぞれの $i$ について $S$ と $S[i,|S|]$ の最長共通接頭辞の長さを記録した配列を線形時間で構築するアルゴリズムである。

具体例を以下に示す。例えば $i = 5$ のときの最長共通接頭辞は “aaa”, つまり $3$ 文字である。

aaabaaaab
921034210

計算量

• $O(|S|)$

実装例

vector< int > z_algorithm(const string &s) {
  vector< int > prefix(s.size());
  for(int i = 1, j = 0; i < s.size(); i++) {
    if(i + prefix[i - j] < j + prefix[j]) {
      prefix[i] = prefix[i - j];
    } else {
      int k = max(0, j + prefix[j] - i);
      while(i + k < s.size() && s[k] == s[i + k]) ++k;
      prefix[i] = k;
      j = i;
    }
  }
  prefix[0] = (int) s.size();
  return prefix;
}