Zアルゴリズムとは？仕組みとC++実装例をわかりやすく解説

Zアルゴリズム（Z Algorithm）は、その名の通り「Z配列（Z Array）」を作成することで文字列検索を実現するアルゴリズムです。Z配列のサイズは主文字列（テキスト）と同じであり、各位置から始まる部分文字列のうち、文字列の先頭と一致する最長の長さを格納します。

処理の最初に、パターンと主テキストを、両者に含まれない特殊な記号で連結します。パターンをP、主テキストをTとすると、連結後の文字列は P$T のようになります（ここでは $ がPにもTにも含まれていないものと仮定します）。

このアルゴリズムの計算量は O(m+n) です。m はパターンの長さ、n は主文字列の長さを表します。

入力と出力

Input:
Main String: "ABAAABCDBBABCDDEBCABC", Pattern: "ABC"
Output:
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

アルゴリズム

fillZArray(conStr, ZArray)

入力 − conStr はパターンと主テキストを連結した文字列です。ZArray には、先頭と一致する最長部分文字列の長さを格納します。

出力 − 値が埋められた ZArray

Begin
    n := length of conStr
    windLeft := 0 and windRight := 0

    for i := 1 to n, do
       if i > windRight, then
          windLeft := i and windRight := i
          while windRight < n AND conStr[windRight-windLeft] =
             conStr[windRight], do
             increase windRight by 1
          done
          ZArray[i] := windRight – windLeft
          decrease windRight by 1
       else
          k := i – windLeft
          if ZArray[k] < windRight – i +1, then
             ZArray[i] := ZArray[k]
          else
             windLeft := i
             while windRight < n AND conStr[windRight-windLeft] =
                conStr[windRight], do
                increase windRight by 1
             done
             ZArray[i] := windRight – windLeft
             decrease windRight by 1
   done
End

zAlgorithm(text, pattern)

入力 − 主テキストと検索対象のパターン

出力 − パターンが見つかった位置

Begin
    conStr = concatenate pattern + "$" + text
    patLen := length of pattern
    len := conStr length
    fillZArray(conStr, ZArray)

    for i := 0 to len – 1, do
       if ZArray[i] = patLen, then
          print the location i – patLen – 1
    done
End

C++による実装例

#include<iostream>
using namespace std;

void fillZArray(string conStr, int zArr[]) {
    int n = conStr.size();
    int windLeft, windRight, k;
    windLeft = windRight = 0;      //initially window size is 0

    for(int i = 1; i < n; i++) {
       if(i > windRight) {
          windLeft = windRight = i;     //window size is 0 but position to i
          while(windRight < n && conStr[windRight-windLeft] == conStr[windRight]) {
             windRight++;     //extend the right bound of window
          }
          zArr[i] = windRight-windLeft;
          windRight--;
       }else {
          k = i-windLeft;
          if(zArr[k] < windRight-i+1)
             zArr[i] = zArr[k];     //when kth item less than remaining interval
          else {
             windLeft = i;
             while(windRight < n && conStr[windRight - windLeft] == conStr[windRight]) {
                windRight++;
             }
             zArr[i] = windRight - windLeft;
             windRight--;
          }
       }
    }
}

void zAlgorithm(string mainString, string pattern, int array[], int *index) {
    string concatedStr = pattern + "$" + mainString;     //concat with special character
    int patLen = pattern.size();
    int len = concatedStr.size();
    int zArr[len];
    fillZArray(concatedStr, zArr);

    for(int i = 0; i<len; i++) {
       if(zArr[i] == patLen) {
          (*index)++;
          array[(*index)] = i - patLen -1;
       }
    }
}

int main() {
    string mainString = "ABAAABCDBBABCDDEBCABC";
    string pattern = "ABC";
    int locArray[mainString.size()];
    int index = -1;
    zAlgorithm(mainString, pattern, locArray, &index);

    for(int i = 0; i <= index; i++) {
       cout << "Pattern found at position: " << locArray[i]<<endl;
    }
}

実行結果

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18