在这个问题中,我们给两个字符串一个文本和一个模式。我们的任务是为KMP算法创建一个用于模式搜索的程序,它将找到文本字符串中所有出现的模式。
在这里,我们必须找到文本中所有模式的出现。
让我们举个例子来了解这个问题,
text = “xyztrwqxyzfg” pattern = “xyz”
输出结果
Found at index 0 Found at index 7
在这里,我们将讨论使用KMP(Knuth Morris Pratt)模式搜索算法解决问题的方法,它将使用模式的预处理字符串,该字符串将用于文本匹配。如果匹配字符后跟不匹配模式的字符串字符,则帮助处理或查找模式匹配。
我们将对模式棒进行预处理,以创建一个数组,其中包含该模式的正确前缀和后缀,这将有助于查找不匹配的模式。
//用于模式搜索的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