โปรแกรม C สำหรับอัลกอริทึม KMP ในการค้นหา Pattern

ในปัญหานี้ เราได้รับสตริง 2 ตัวคือ text และ pattern งานของเราคือสร้างโปรแกรมสำหรับอัลกอริทึม KMP ในการค้นหา pattern เพื่อหาทุกครั้งที่ pattern ปรากฏใน text string

ที่นี่ เราต้องหาทุกครั้งที่ pattern ปรากฏใน text

มาดูตัวอย่างเพื่อเข้าใจปัญหา

อินพุต

text = "xyztrwqxyzfg" pattern = "xyz"

เอาต์พุต

Found at index 0 Found at index 7

ที่นี่ เราจะอภิปรายวิธีแก้ปัญหาโดยใช้ KMP (Knuth Morris Pratt) pattern searching algorithm ซึ่งจะใช้การประมวลผลสตริง pattern ล่วงหน้า (preprocessing) เพื่อสร้างอาร์เรย์ที่มี proper prefix และ suffix จาก pattern ซึ่งจะช่วยในการหา pattern mismatch

เราจะทำ preprocessing กับ pattern เพื่อสร้างอาร์เรย์ที่มี proper prefix และ suffix จาก pattern ที่จะช่วยในการหา pattern mismatch

โปรแกรมสำหรับอัลกอริทึม KMP ในการค้นหา Pattern

// C Program for KMP Algorithm for Pattern Searching

ตัวอย่าง

#include<iostream>
#include<string.h>
using namespace std;
void prefixSuffixArray(char* pat, int M, int* pps) {
    int length = 0;
    pps[0] = 0;
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[length]) {
            length++;
            pps[i] = length;
            i++;
        } else {
            if (length != 0)
                length = pps[length - 1];
            else {
                pps[i] = 0;
                i++;
            }
        }
    }
}
void KMPAlgorithm(char* text, char* pattern) {
    int M = strlen(pattern);
    int N = strlen(text);
    int pps[M];
    prefixSuffixArray(pattern, M, pps);
    int i = 0;
    int j = 0;
    while (i < N) {
        if (pattern[j] == text[i]) {
            j++;
            i++;
        }
        if (j == M) {
            printf("Found pattern at index %d\n", i - j);
            j = pps[j - 1];
        }
        else if (i < N && pattern[j] != text[i]) {
            if (j != 0)
                j = pps[j - 1];
            else
                i = i + 1;
        }
    }
}
int main() {
    char text[] = "xyztrwqxyzfg";
    char pattern[] = "xyz";
    printf("The pattern is found in the text at the following index : \n");
    KMPAlgorithm(text, pattern);
    return 0;
}

ผลลัพธ์

The pattern is found in the text at the following index −

Found pattern at index 0
Found pattern at index 7