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