อัลกอริทึม Z (Z Algorithm) สำหรับการค้นหาแพทเทิร์น

บทนำ

อัลกอริทึม Z เรียกเช่นนี้เพราะต้องสร้างอาร์เรย์ Z ซึ่งมีขนาดเท่ากับความยาวของข้อความ (Text) อาร์เรย์นี้เก็บความยาวของสตริงย่อย (Substring) ที่ยาวที่สุดที่เริ่มจากตัวอักษรปัจจุบันของข้อความหลัก

ขั้นแรก รวมแพทเทิร์น (Pattern) และข้อความหลัก (Text) ด้วยสัญลักษณ์พิเศษที่ไม่ปรากฏในทั้งสอง เช่น P$T (ถ้า $ ไม่อยู่ใน P และ T)

ความซับซ้อนของเวลา (Time Complexity)

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)

Input: conStr = สตริงที่รวมแล้ว (Pattern + $ + Text), ZArray = อาร์เรย์เก็บความยาว substring ยาวที่สุด
Output: ZArray ที่เติมค่าแล้ว

Begin
    n := ความยาวของ conStr
    windLeft := 0, windRight := 0
    for i := 1 ถึง n do
        if i > windRight then
            windLeft := i, windRight := i
            while windRight < n AND conStr[windRight-windLeft] = conStr[windRight] do
                เพิ่ม windRight 1
            done
            ZArray[i] := windRight - windLeft
            ลด windRight ลง 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
                    เพิ่ม windRight 1
                done
                ZArray[i] := windRight - windLeft
                ลด windRight ลง 1
        done
End

zAlgorithm(text, pattern)

Input: ข้อความหลักและแพทเทิร์นที่ต้องการค้นหา
Output: ตำแหน่งที่พบแพทเทิร์น

Begin
    conStr = pattern + "$" + text
    patLen := ความยาวของ pattern
    len := ความยาวของ conStr
    fillZArray(conStr, ZArray)
    for i := 0 ถึง len-1 do
        if ZArray[i] = patLen then
            พิมพ์ตำแหน่ง i - patLen - 1
    done
End

ตัวอย่างโค้ด (C++)

#include<iostream>
using namespace std;

void fillZArray(string conStr, int zArr[]) {
    int n = conStr.size();
    int windLeft, windRight, k;
    windLeft = windRight = 0;
    for(int i = 1; i < n; i++) {
        if(i > windRight) {
            windLeft = windRight = i;
            while(windRight < n && conStr[windRight-windLeft] == conStr[windRight]) {
                windRight++;
            }
            zArr[i] = windRight-windLeft;
            windRight--;
        } else {
            k = i-windLeft;
            if(zArr[k] < windRight-i+1)
                zArr[i] = zArr[k];
            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;
    int patLen = pattern.size();
    int len = concatedStr.size();
    int zArr[len];
    fillZArray(concatedStr, zArr);
    for(int i = 0; i

ผลลัพธ์
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18