使用c语言实现kmp算法代码
时间: 2023-10-16 13:11:43 浏览: 115
以下是使用C语言实现KMP算法的代码:
```c
#include <stdio.h>
#include <string.hvoid computeLPSArray(char* pat, int M, int* lps)
{
int len = 0; // length of the previous longest prefix suffix
lps[0] = 0; // lps[0] is always 0
int i = 1;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0) {
len = lps[len - 1];
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}
void KMPSearch(char* pat, char* txt)
{
int M = strlen(pat);
int N = strlen(txt);
int lps[M];
computeLPSArray(pat, M, lps);
int i = 0; // index for txt[]
int j = 0; // index for pat[]
while (i < N) {
if (pat[j] == txt[i]) {
j++;
i++;
}
if (j == M) {
printf("Found pattern at index %d\n", i - j);
j = lps[j - 1];
}
// mismatch after j matches
else if (i < N && pat[j] != txt[i]) {
// Do not match lps[0..lps[j-1]] characters,
// they will match anyway
if (j != 0) {
j = lps[j - 1];
}
else {
i = i + 1;
}
}
}
}
int main()
{
char txt[] = "ABABDABACDABABCABAB";
char pat[] = "ABABCABAB";
KMPSearch(pat, txt);
return 0;
}
```
这个示例代码中,`computeLPSArray`函数用于计算模式串的最长前缀后缀的长度,`KMPSearch`函数用于在文本串中查找模式串。
阅读全文