KMP
#include <stdio.h>#include <string.h>
typedef char* String;
void get_next(String a,int *next)
{ int i=0,j=1;
next=0;
while(j<a)
{
if(i==0||a==a)
{
i++;
j++;
if(a!=a)
{
next=i;
}
else
{
next=next;
}
}
else
{
i=next;
}
}
}
void init_kmp(String a,String b)
{
int next;
int i=1,j=1;
get_next(b,next);
while(i<=a)
{
while(i<=a&&j<=b)
{
if(j==0||a==b)
{
i++;
j++;
}
else
{
j=next;
}
}
if(j>b)
{
printf("%d\n",i-b);
}
else
{
printf("%d",0);
}
j=0;
}
}
void main()
{
char a=" BBC ABCDABCDABDAB ABCDABCDABDEABCDABD";
char b=" ABCDABD";
a=(int)(strlen(a))-1;
b=(int)(strlen(b))-1;
init_kmp(a,b);
}
大侠帮忙看看，哪里需要改进的地方，虽然写出来了，但是貌似有个别点还是有点模糊，其中有的还是参考别人的写出来的。 骇客king 发表于 2015-8-24 21:49
返回1,7 不对吗？应该就是返回7和1啊
你要是想返回2和8 就在,i-b 加1就行了
我刚才调试了一下我知道原因了 我之前觉得是1 3 7 楼主 我想问问你 i-b是什么意思啊？ i为当前主串配比成功的位置，减去模式串的总长度，就是模式串在主串中的位置了，可以再加+1，就得出第一个匹配的位置，b就是模式串的长度了。
为什么这么问呢？ 如果a="ababaaaba"
b="aba"
输出为什么是1和7呢？ leonardzzy 发表于 2015-8-24 17:43
如果a="ababaaaba"
b="aba"
输出为什么是1和7呢？
我没上机 现在手机看的串的第一个字符要填写串长度不知道你填了吗 如果填了 我明天看看哪里有问题 你能帮忙看看哪有问题吗 本帖最后由 骇客king 于 2015-8-24 21:52 编辑
骇客king 发表于 2015-8-24 21:21
我没上机 现在手机看的串的第一个字符要填写串长度不知道你填了吗 如果填了 我明天看看哪里有问题 你 ...
返回1,7 不对吗？应该就是返回7和1啊
你要是想返回2和8 就在,i-b 加1就行了
1和7是对整个数组说话的，因为最前边是存放的是串的长度，要占一个位置的，你可以手动加上1，或心理加一个，哈哈
应该有更好的方法，不需要第一个元素放串长度，用结构是不是有点浪费，还有如果要动态串长度，是不是就得用结构了，封装到一个dll里，以后调用就方便了。 建议看看数据结构里的 KMP。 不错不错，我原理懂了，但写起来也有点模糊 感谢楼主的奉献 我要鱼币 我 是来得鱼币的 没有问题！
页:
[1]