Zアルゴリズム

このアルゴリズムでは、Z配列を作成する必要があるため、このアルゴリズムはZアルゴリズムと呼ばれます。 Z配列のサイズは、テキストサイズと同じです。この配列は、メイン文字列の現在の文字から始まる可能な最長のサブ文字列の長さを格納するために使用されます。最初に、パターンと本文は、テキストとパターンに存在しない特別な記号で連結されます。 Pがパターンで、Tが本文の場合、連結後はP $ Tになります（$がPとTに存在しないと仮定します）。

このアルゴリズムの場合、mはパターンの長さ、nはメイン文字列の長さであるため、時間計算量はO（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（テキスト、パターン）

入力- メインテキストと検索するパターン

出力- パターンが見つかった場所

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

例

#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