如何理解KMP算法中求next函数值的算法

我在课本上看到作者定义了一个函数去求next函数值:
void get_next(SString T,int &next[]){....},请问第二个参数是什么意思?调用该函数时如何传递实参?使用时需不需要包含头文件?我用的平台是VC.请详细介绍,谢谢!!最好能举例说明.
最后恳请哪位高手能不能用KMP算法来实现一个具体的实例.请用完整的代码演示,一定要可以编译运行哟!

15 个解决方案

#1

帮帮我!!!

#2

help !!!

#3

help

#4

编写一个函数char*findchar（char *s,char *t),用于查找字符串t在字符串s中最右边出现的位置，如果没有找到则返回NULL，并编写一个主程序来测试该函数。在主程序中按行输入两个字符串，并输出查找结果.

我用的是KMP演算法.

#include <iostream> 
#include <string> 

using namespace std; 

int findchar(const char *s,const char *t, int pos); 
int* get_next(const char *t);

int main(int argc, char* argv[]) 
{ 
string s; 
string t; 
cout<<"输入第一个字符串(以输入#结束): \b"; 
getline(cin,s,'#'); 
cout<<"输入第一个字符串(以输入#结束): \b"; 
getline(cin,t,'#'); 
int pos = findchar(s.c_str(),t.c_str(),0);
int flag = 0;
flag = pos;
if (pos == 0)
{
   cout<<"失败!"<<endl;
}
else while (pos != 0 && (pos < s.length()))
{
   flag = pos;
   pos = findchar(s.c_str(),t.c_str(),pos);
  
   if (pos == 0)
    break;
}
if (flag !=0)
{
   cout<<"成功!在"<<flag<<"找到."<<endl;
}

return EXIT_SUCCESS; 
} 
int findchar(const char *s,const char *t, int pos) 
{
int i=pos;
int j=0;
int S=strlen(s);
int T=strlen(t);
int *next=get_next(t);
while(i<S&&j<T)
{
   if(j==0||s[i]==t[j])
   {
    i++;
    j++;
   }
   else
    j=next[j];
}
if(j>=T)
{
   pos = i-T+2;
   return pos;
}
else
{
   return 0;
}
}
int* get_next(const char *t)
{
int i=1;
int next[100];
next[1]=0;
int j=0;
while(i<strlen(t))
{
   if(j==0||t[i]==t[j])
   {
    i++;
    j++;
    next[i]=j;
   }
   else
    j=next[j];
}
return next;
}

#5

vc 6.0 sp 6通過了.

#6

在get_next中,返回局部非静态变量的指针.怕是不对嘎.

#7

支持搂主，收藏

#8

http://blog.csdn.net/Supercaller/archive/2008/05/25/2479550.aspx我自己写了个求kmp算法中的next函数值，大家可以给点意见

#9

还是不理解。呵呵

#10

我也搞了很久，后来发现一个更容易理解，也更搞笑的算法
 sunday算法http://blog.csdn.net/Java2King/archive/2010/01/30/5273599.aspx

#11

更加高效~~

#12

sunday虽好，但其算法思想局限于单模式匹配，而kmp的next思想应用到后缀树上，就是多模式匹配了。

#13

引用 12 楼 litaoye 的回复:

sunday虽好，但其算法思想局限于单模式匹配，而kmp的next思想应用到后缀树上，就是多模式匹配了。

trie+kmp建立的前缀树，简直是强捍，多串匹配达到线性的速度...

#14

这是计算串的next值代码：
#include<iostream>
using namespace std;
void Getnext(char str[],int next[])
{
int i = 0,j = -1;
next[0] = -1;
while(i < strlen(str))
{
if(j == -1 || str[i] == str[j])
{
i++;
j++;
next[i] = j;
}
else
{
j = next[j];
}
}
}
int main()
{
char str[100];
int next[100];
cin>>str;
Getnext(str,next);
int i;
for(i = 0; i < strlen(str); i++)
{
cout<<next[i];
}
cout<<endl;
return 0;
}

输入：abbabcacba
输出:-1000120100

#15

看代码有什么作用，关键是理解没有？看数据结构，严蔚敏老师那本，我觉得写的很清楚了！