ei1333's page

ホーム > Wiki

Z-algorithm

説明

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

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

aaabaaaab
921034210

計算量

$O(|S|)$

実装例

struct Z_algorithm
{
  vector< int > prefix;

  void build(const string &s)
  {
    prefix.assign(s.size(), 0);
    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();
  }

  int operator[](const int k) const
  {
    return (prefix[k]);
  }

  size_t size()
  {
    return(prefix.size());
  }
};

問題例

参考資料