อัลกอริทึม Z (Linear Time Pattern Searching Algorithm) ใน C++

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

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

Z Array

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

อัลกอริทึม

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

เราจะสร้าง z array ต่อมา อัลกอริทึมจะวนลูปผ่านทุกตัวอักษรของสตริงด้วย i = 1 ถึง n-1 ตอนนี้เราจะสร้างสตริงย่อย s[L-R] ซึ่งเป็นคำนำหน้าสตริงย่อย (prefix substring) ที่ทำให้ 1 ≤ L ≤ i ≤ R

ตอนนี้ สำหรับช่วงที่ถูกต้องในการสร้างสตริงย่อย [L, R] สำหรับ i-1 และค่า z ทั้งหมดจนถึง i-1 คำนวณ z[i] และช่วงใหม่ [L, R] โดยใช้ขั้นตอนต่อไปนี้:

ขั้นตอนที่ 1: หาก i > R ไม่มีคำนำหน้าสตริงย่อยที่ใหญ่กว่าเป็นไปได้ ดังนั้นเราจะคำนวณช่วงใหม่โดยเปรียบเทียบ S[0] กับ S[i] คือสตริงเริ่มจากดัชนี 0 (จุดเริ่มต้น) กับสตริงย่อยเริ่มจากดัชนี i และหา z[i] โดยใช้ z[i] = R - L + 1
ขั้นตอนที่ 2: มิฉะนั้น หาก i ≤ R [L, R] สามารถขยายได้ถึง i สำหรับ k = i-L, z[i] ≥ min(Z[k], R-i+1)
    ขั้นตอนที่ 2.1: หาก Z[k] < R-i+1 ไม่มีสตริงย่อยที่ยาวกว่าสำหรับ s[i]
    ขั้นตอนที่ 2.2: หาก Z[k] ≥ R-i+1 แล้วอาจมีสตริงย่อยที่ยาวกว่า ดังนั้นเราจะอัปเดต [L, R] โดยเปลี่ยน L = i และเปลี่ยน R โดยการจับคู่จาก 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 pattern '" << pattern << "' is found in the string '" << str << "' at index \t";
    zAlgorithm(str, pattern);
    return 0;
}

ผลลัพธ์

The pattern ' tutorial ' is found in the string 'Hello! Welcome To tutorials Point programming tutorial ' at index 18 46