อัลกอริทึม Z (อัลกอริทึมการค้นหารูปแบบเวลาเชิงเส้น) ใน C ++

อัลกอริทึม Z ใช้เพื่อค้นหาการเกิดขึ้นของรูปแบบในสตริงในเวลาเชิงเส้น สมมติว่าความยาวของสตริงเป็น n และขนาดของรูปแบบที่จะค้นหาคือ m เวลาในการแก้ไขจะอยู่ในลำดับ O(m+n) .

อัลกอริทึม z ใช้อาร์เรย์ Z เพื่อค้นหารูปแบบที่เกิดขึ้น

อาร์เรย์ Z

เป็นอาร์เรย์ที่มีความยาวเท่ากับสตริง แต่ละองค์ประกอบของ z-array ประกอบด้วยความยาวของสตริงย่อยที่ยาวที่สุดของสตริงโดยเริ่มจาก I ซึ่งสามารถใช้เป็นคำนำหน้าของสตริงได้

อัลกอริทึม

ในอัลกอริทึมนี้ เราจะได้รับสตริง S ที่มีความยาว n และรูปแบบที่จะค้นหา p ที่มีความยาว m

เราจะสร้างอาร์เรย์ z ตอนนี้ อัลกอริธึมวนรอบอักขระทั้งหมดของสตริงด้วย i =1 ถึง n-1 ตอนนี้ เราจะสร้างสตริงย่อย s[L-R] ซึ่งเป็นสตริงย่อยส่วนนำหน้า โดยที่ 1 ≤ L ≤ I ≤ R

สำหรับช่วงเวลาที่ถูกต้องสำหรับการสร้างสตริงย่อย [L, R] สำหรับ i-1 และค่า z ทั้งหมดจนถึง i-1 คำนวณ 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