ในปัญหานี้ เราได้รับข้อความและรูปแบบสองสตริง งานของเราคือสร้างโปรแกรมสำหรับอัลกอริทึม KMP สำหรับการค้นหารูปแบบ โดยจะค้นหารูปแบบที่เกิดขึ้นทั้งหมดในสตริงข้อความ
ที่นี่ เราต้องหารูปแบบที่เกิดขึ้นทั้งหมดในข้อความ
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
text = “xyztrwqxyzfg” pattern = “xyz”
ผลลัพธ์
Found at index 0 Found at index 7
เราจะพูดถึงวิธีแก้ปัญหาโดยใช้ KMP (Knuth Morris Pratt ) อัลกอริธึมการค้นหารูปแบบ จะใช้สตริงการประมวลผลล่วงหน้าของรูปแบบ ซึ่งจะใช้สำหรับการจับคู่ในข้อความ และช่วยในการประมวลผลหรือค้นหารูปแบบที่ตรงกันในกรณีที่อักขระที่ตรงกันตามด้วยอักขระของสตริงที่ไม่ตรงกับรูปแบบ
เราจะประมวลผลแพทเทิร์น wand ล่วงหน้าเพื่อสร้างอาร์เรย์ที่มีคำนำหน้าและส่วนต่อท้ายที่เหมาะสมจากรูปแบบที่จะช่วยในการค้นหารูปแบบที่ไม่ตรงกัน
โปรแกรมสำหรับอัลกอริทึม KMP สำหรับการค้นหารูปแบบ
// โปรแกรม C สำหรับอัลกอริทึม KMP สำหรับการค้นหารูปแบบ
ตัวอย่าง
#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;
} ผลลัพธ์
พบรูปแบบในข้อความที่ดัชนีต่อไปนี้ -
Found pattern at index 0 Found pattern at index 7
