数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学KMP 算法模式搜索的 C 程序
在这个问题中，我们得到了两个字符串，一个文本和一个模式。我们的任务是创建一个用于模式搜索的 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
", 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 :
");
KMPAlgorithm(text, pattern);
return 0;
}输出
模式在以下索引处的文本中找到 -
Found pattern at index 0 Found pattern at index 7
更新于: 2020-07-17
8K+ 次查看
广告