이 문제에서는 두 개의 문자열 텍스트와 패턴이 제공됩니다. 우리의 임무는 패턴 검색을 위한 KMP 알고리즘을 위한 프로그램을 만드는 것입니다. 이 프로그램은 텍스트 문자열에서 패턴의 모든 항목을 찾을 것입니다.
여기서 우리는 텍스트에서 모든 패턴의 발생을 찾아야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
text = “xyztrwqxyzfg” pattern = “xyz”
출력
Found at index 0 Found at index 7
여기에서는 KMP(Knuth Morris Pratt ) 패턴 검색 알고리즘의 경우 텍스트에서 일치하는 데 사용할 패턴의 전처리 문자열을 사용합니다. 그리고 일치하는 문자 뒤에 패턴과 일치하지 않는 문자열의 문자가 오는 경우 패턴 일치를 처리하거나 찾는 데 도움이 됩니다.
패턴 막대를 사전 처리하여 불일치 패턴을 찾는 데 도움이 되는 패턴의 적절한 접두사와 접미사를 포함하는 배열을 만듭니다.
패턴 검색을 위한 KMP 알고리즘 프로그램
// 패턴 검색을 위한 KMP 알고리즘을 위한 C 프로그램
예시
#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