C++のZアルゴリズムとは？線形時間でパターン検索を行う手法を実装付きで解説

Zアルゴリズムは、文字列の中に特定のパターンが出現する位置を線形時間で検索するためのアルゴリズムです。文字列の長さを n、検索したいパターンのサイズを m とすると、計算にかかる時間は O(m+n) のオーダーに収まります。

Zアルゴリズムでは、「Z配列」と呼ばれるデータ構造を利用してパターンの出現位置を効率よく見つけます。

Z配列とは

Z配列は、元の文字列と同じ長さを持つ配列です。各要素には、文字列の i 番目の位置から始まる部分文字列のうち、文字列そのものの接頭辞（プレフィックス）と一致する最長の長さが格納されます。

例えば、文字列 "aabxaabxcaabxaabxay" の場合、各位置における「先頭からの一致長」を記録することで、後続の照合処理を大幅に高速化できます。

アルゴリズムの手順

このアルゴリズムでは、長さ n の文字列 S と、検索対象となる長さ m のパターン p が与えられます。

まず Z 配列を作成します。その後、i = 1 から n-1 まで文字列の各文字に対してループ処理を行い、1 ≤ L ≤ i ≤ R を満たすような接頭辞部分文字列 s[L-R] を管理していきます。

i-1 までの有効な区間 [L, R] とそこまでの Z 値をもとに、以下の手順で z[i] および新しい区間 [L, R] を計算します。

ステップ1：i > R の場合
　それ以上大きな接頭辞部分文字列は存在しません。
　そこで、S[0]（先頭から始まる文字列）と S[i]（インデックス i から始まる部分文字列）を比較して新しい区間を求め、
　z[i] = R - L + 1 として z[i] を計算します。

ステップ2：i ≤ R の場合
　区間 [L, R] は i まで拡張できます。k = i - L のとき、z[i] ≥ min(Z[k], R-i+1) が成り立ちます。
　・ステップ2.1：Z[k] < R-i+1 の場合 → より長い接頭辞部分文字列 s[i] は存在しません。
　・ステップ2.2：Z[k] ≥ R-i+1 の場合 → より長い部分文字列が存在する可能性があります。
　　このとき L = i と更新し、S[R+1] 以降を照合しながら R を伸ばして [L, R] を更新します。

このプロセスにより、たった一回のループ処理ですべての Z 値を求めることができます。これが O(n) の線形時間を実現する鍵となっています。

パターン検索への応用

実際のパターン検索では、「パターン + 区切り文字（$など）+ テキスト」という新しい文字列を作成し、その Z 配列を計算します。Z 値がパターンの長さと一致した位置が、テキスト内でのパターンの出現位置に対応します。

実装例

以下は、ZアルゴリズムをC++で実装したプログラムです。

#include<iostream>
using namespace std;
void createZarray(string str, int Z[]){
   int n = str.length();
   int L, R, k;
   L = R = 0;
   for (int i = 1; i < n; ++i){
      if (i > R){
         L = R = i;
         while (R<n && str[R-L] == str[R])
         R++;
         Z[i] = R-L;
         R--;
      } else {
         k = i-L;
         if (Z[k] < R-i+1)
            Z[i] = Z[k];
         else {
            L = i;
            while (R<n && str[R-L] == str[R])
               R++;
            Z[i] = R-L;
            R--;
         }
      }
   }
}
void zAlgorithm(string text, string pattern){
   string str = pattern+"$"+text;
   int len = str.length();
   int Z[len];
   createZarray(str, Z);
   for (int i = 0; i < len; ++i){
      if (Z[i] == pattern.length())
         cout<<(i-pattern.length()-1)<<"\t";
   }
}
int main(){
   string str = "Hello! Welcome To tutorials Point programming tutorial";
   string pattern = "tutorial";
   cout<<"The patter ' "<<pattern<<" ' is found in the string '"<<str<<" ' at index \t";
   zAlgorithm(str, pattern);
   return 0;
}

実行結果

The patter ' tutorial ' is found in the string 'Hello! Welcome To tutorials Point programming tutorial ' at index 18 46

この実行結果から、パターン "tutorial" はテキスト内のインデックス 18 と 46 の2箇所に出現していることがわかります。Zアルゴリズムを使えば、このように複数の出現位置も効率よく検出できます。