Z Algorithm

อัลกอริทึมนี้มีชื่อว่า Z Algorithm เพราะในอัลกอริทึมนี้ เราจำเป็นต้องสร้างอาร์เรย์ Z ขนาดของอาร์เรย์ Z เท่ากับขนาดข้อความ อาร์เรย์นี้ใช้เพื่อเก็บความยาวของสตริงย่อยที่ยาวที่สุดที่เป็นไปได้โดยเริ่มจากอักขระปัจจุบันของสตริงหลัก ในตอนแรก รูปแบบและข้อความหลักจะถูกเชื่อมด้วยสัญลักษณ์พิเศษซึ่งไม่มีอยู่ในข้อความและรูปแบบ หาก P คือรูปแบบ และ T เป็นข้อความหลัก หลังจากต่อกันแล้ว มันจะเป็น P$T (สมมติว่า $ ไม่มีอยู่ใน P และ T)

สำหรับอัลกอริทึมนี้ ความซับซ้อนของเวลาคือ O(m+n) เนื่องจาก 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