我有下一个 KMP 实现:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int kmp(char substr[], char str[])
{
int i, j, N, M;
N = strlen(str);
M = strlen(substr);
int *d = (int*)malloc(M * sizeof(int));
d[0] = 0;
for(i = 0, j = 0; i < M; i++)
{
while(j > 0 && substr[j] != substr[i])
{
j = d[j - 1];
}
if(substr[j] == substr[i])
{
j++;
d[i] = j;
}
}
for(i = 0, j = 0; i < N; i++)
{
while(j > 0 && substr[j] != str[i])
{
j = d[j - 1];
}
if(substr[j] == str[i])
{
j++;
}
if(j == M)
{
free(d);
return i - j + 1;
}
}
free(d);
return -1;
}
int main(void)
{
char substr[] = "World",
str[] = "Hello World!";
int pos = kmp(substr, str);
printf("position starts at: %i\r\n", pos);
return 0;
}
您可以在这里进行测试:http://liveworkspace.org/code/d2e7b3be72083c72ed768720f4716f80
它在小字符串上效果很好,我用大循环测试过,这样一切都很好。
但是如果我将要搜索的子字符串和完整的字符串更改为这些:
char substr[] = "%end%",
str[] = "<h1>The result is: <%lua% oleg = { x = 0xa }
table.insert(oleg, y) oleg.y = 5 print(oleg.y) %end%></h1>";
只有在第一次尝试之后,这个实现才会失败......
拜托,你能帮我修复 KMP 的实现,使算法能够处理字符串中的此类数据吗...
最佳答案
在一个地方你偏离了你的来源,来源有
while(j>0 && p[j]!=p[i]) j = d[j-1];
if(p[j]==p[i])
j++;
d[i]=j;
当你有
while(j > 0 && substr[j] != substr[i])
{
j = d[j - 1];
}
if(substr[j] == substr[i])
{
j++;
d[i] = j;
}
被来源的缩进所欺骗。在源代码中,if()
分支没有大括号,因此只有增量 j++;
由 if
控制; d[i] = j;
是无条件的。
然后,来源有错误,可能是由于索引的不正常使用。正确的数组设置方法是
int *d = (int*)malloc(M * sizeof(int));
d[0] = 0;
for(i = 1, j = 0; i < M; i++)
{
while(j > 0 && substr[j-1] != substr[i-1])
{
j = d[j - 1];
}
if(substr[j] == substr[i])
j++;
d[i] = j;
}
但这很令人困惑,因为这里的设置使用了索引 i-1
和 j-1
以及 i
和 j
来确定 d[i]
。通常的实现方式不同;它的实现方式in C# .由于这是您在大多数来源中找到的形式,因此让自己相信它的正确性要容易得多。
关于c - 纯 C 中的 Knuth-Morris-Pratt 实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11257652/