最長共通接頭辞（Z-Algorithm）のライブラリを作った

今まで文字列照合系問題は、DP(LCS)で頑張っていたけど、持っていたら便利そうだと思ったのでライブラリを用意してみた。

前提

Z-Algorithmとは、最長共通接頭辞の長さを線形時間で求めるアルゴリズム。

• 文字列の長さをnとして、O(n²)を、O(n)に改善できる
• 既に算出済みの長さを利用して効率化を図る
• 基本的な発想は、Z[i]:=iからの共通接頭辞の長さ、として、Z[i], Z[j]の値が一致するなら、i < i+k < i+Z[j] なるkについて、Z[j+k] は Z[i+k] に一致するから再利用しようというもの
• 例外が2つある
  • i側であるindex:x(∈[i+1,i+Z[i]])を定めた時、xから始まる共通接頭辞がi+Z[i]を超える場合
  • j側でも同様に、j+Z[j]を超えて一致する場合

Z-Algorithmのわかりやすい解説

snuke.hatenablog.com

scrapbox.io

実装

// Z-Algorithm
vector<int> Z;

int z_algorithm(const string& s){
  int n=s.size();
  Z.clear();
  Z.resize(n);
  
  Z[0]=n;
  int i=1, j=0; // i:今見ているindex, j:iから一致する共通接頭辞の長さ
  while(i<n){
    while(i+j<n and s[j]==s[i+j]) j++; // iから愚直に接頭辞の長さを求める
    Z[i]=j;
    if(j==0){
      i++;
      continue;
    }
    int k=1;
    while(i+k<n and k+Z[k]<j){ // Z[k]からの長さがjに完全に含まれるなら（終端は含まない）、Z[i+k]はZ[k]と一致する
      Z[i+k]=Z[k];
      k++;
    }
    i+=k; // Z[i+k]=Z[k]で埋めた最後のindexの次にカーソルを移動
    j-=k; // [i,i+j]は共通接頭辞で、前からkまで検査済みなので、Z[i+k]は少なくともj-k以上になる
  }
  
  return *max_element(Z.begin(), Z.end());
}

検証用問題

atcoder.jp