Trong bài toán này, chúng ta có hai chuỗi một văn bản và một mẫu. Nhiệm vụ của chúng tôi là tạo một chương trình cho thuật toán KMP để tìm kiếm mẫu, nó sẽ tìm tất cả các lần xuất hiện của mẫu trong chuỗi văn bản.
Ở đây, chúng ta phải tìm tất cả các lần xuất hiện của các mẫu trong văn bản.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
text = “xyztrwqxyzfg” pattern = “xyz”
Đầu ra
Found at index 0 Found at index 7
Ở đây, chúng ta sẽ thảo luận về giải pháp cho vấn đề bằng cách sử dụng KMP ( Knuth Morris Pratt ) thuật toán tìm kiếm mẫu, nó sẽ sử dụng một chuỗi tiền xử lý của mẫu sẽ được sử dụng để đối sánh trong văn bản. Và trợ giúp trong việc xử lý hoặc tìm các kết quả phù hợp với mẫu trong trường hợp các ký tự phù hợp được theo sau bởi ký tự của chuỗi không khớp với mẫu.
Chúng tôi sẽ xử lý trước đũa phép mẫu để tạo một mảng có chứa tiền tố và hậu tố thích hợp từ mẫu sẽ giúp tìm kiếm các mẫu không khớp.
Chương trình cho Thuật toán KMP để Tìm kiếm Mẫu
// Chương trình C cho Thuật toán KMP để tìm kiếm mẫu
Ví dụ
#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;
} Đầu ra
Mẫu được tìm thấy trong văn bản tại chỉ mục sau -
Found pattern at index 0 Found pattern at index 7