C++의 Z 알고리즘(선형 시간 패턴 검색 알고리즘)

Z 알고리즘 선형 시간에 문자열에서 패턴의 발생을 찾는 데 사용됩니다. 문자열의 길이가 n이고 검색할 패턴의 크기가 m인 경우 해결하는 데 걸리는 시간은 O(m+n) 순서가 됩니다. .

z-알고리즘은 Z 배열을 사용하여 패턴의 발생을 찾습니다.

Z 배열

문자열과 길이가 같은 배열입니다. z-array의 각 요소는 문자열 자체의 접두사로 사용할 수 있는 I부터 시작하는 문자열의 가장 긴 부분 문자열의 길이로 구성됩니다.

알고리즘

이 알고리즘에서는 길이가 n인 문자열 S와 길이가 m인 검색할 패턴 p가 제공됩니다.

우리는 z 배열을 만들 것입니다. 이제 알고리즘은 i =1에서 n-1인 문자열의 모든 문자를 반복합니다. 이제 1 ≤ L ≤ I ≤ R과 같은 접두사 부분 문자열인 부분 문자열 s[L-R]를 생성합니다.

이제 i-1 및 i-1까지의 모든 z 값에 대한 부분 문자열 [L, R]을 생성하기 위한 올바른 간격입니다. 다음 단계를 사용하여 z[i]와 새 구간 [L, R]을 계산합니다. -

Step1: if i > R, no larger prefix-substring is possible. So, we will compute new interval bt comparing 
S[0] to S[i] i.e. string starting from index 0 i.e. from start with substring starting from index i. 
And find z[i] using z[i] = R - L + 1.
Step 2: Else if, i ≤ R, [L, R] can be extended to i. For k = i-L, z[i] ≥ min(Z[k], R-i+1).
   Step 2.1: If, Z[k] < R-i+1, no longer prefix substring s[i] exist.
   Step 2.2: If Z[k] ≥ R-i+1, then there can be a longer substring. So, we will update [L, R] by changing L = i and changing R by matching from S[R+1].

이 프로세스는 단일 반복(한 번만 반복)에서 모든 Z 값을 찾습니다.

예시

알고리즘 구현을 보여주는 프로그램 -

#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