Thuật toán Z

Thuật toán này được đặt tên là Thuật toán Z vì trong thuật toán này, chúng ta cần tạo một mảng Z. Kích thước của mảng Z giống với kích thước văn bản. Mảng này được sử dụng để lưu trữ độ dài của chuỗi con dài nhất có thể bắt đầu từ ký tự hiện tại của chuỗi chính. Lúc đầu, mẫu và văn bản chính được nối với nhau bằng một ký hiệu đặc biệt không có trong văn bản và mẫu. Nếu P là mẫu và T là văn bản chính, thì sau khi ghép, nó sẽ là P $ T (Giả sử $ không có trong P và T).

Đối với thuật toán này, độ phức tạp thời gian là O (m + n) vì m là độ dài của mẫu và n là độ dài của chuỗi chính.

Đầu vào và Đầu ra

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

Thuật toán

fillZArray (conStr, ZArray)

Đầu vào - conStr là chuỗi kết hợp của mẫu và văn bản chính. ZArray để lưu trữ các chỉ mục của chuỗi con dài nhất có thể.

Đầu ra - ZArray đầy

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 (văn bản, mẫu)

Đầu vào - Văn bản chính và mẫu để tìm kiếm

Đầu ra - Vị trí tìm thấy mẫu

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

Ví dụ

#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;
   }
}

Đầu ra

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