100分求KMP算法思想。该怎么解决

100分求KMP算法思想。
最近第三次学习KMP算法，依然弄得一头雾水。
在网上找了下资料。发现大部分都不是严蔚敏《数据结构》里的那个版本。
版本一：（《算法导论》）

C/C++ code

void get_next1(){    next1[0] = -1;    int j = -1;    for(int i = 1; i < len; ++i)    {        while(j != -1 && s[j+1] != s[i])            j = next1[j];        if(s[j+1] == s[i])            j++;        next1[i] = j;    }}

版本二：（严蔚敏《数据结构》）

C/C++ code

void get_next2(){    int i = 0;    next2[0] = -1;    int j = -1;    while(i < len)    {        if(j == -1 || s[i] == s[j])        {            ++i;            ++j;            next2[i] = j;        }        else            j = next2[j];    }}

第二个版本我还好理解，就是第一个版本我不明白。

其次，我在POJ 2406做题时，用第二个版本不是TLE就是WA。
题目地址：http://124.205.79.250/JudgeOnline/problem?id=2406

C/C++ code

#include <iostream>using namespace std;char t[1000000];int next[1000000];int len;/*void get_next()    //这个方法是错误的。{    int i = 0;    next[0] = -1;    int j = -1;    while(i < len)    {        if(j == -1 || t[i] == t[j])        {            ++i;            ++j;            next[i] = j;        }        else            j = next[j];    }}*/void get_next() {    next[0] = -1;    int j = -1;    for (int i = 1; i < len; ++i)     {        while (j!= -1 && t[j+1] != t[i])j = next[j];        if (t[j+1] == t[i])j++;        next[i] = j;    }}int main() {    while (scanf("%s",t) && strcmp(t, "."))     {        len = strlen(t);        get_next();                if(len%(len-next[len-1]-1))                  printf("1\n");                else printf("%d\n",len/(len-next[len-1]-1));    }    return 0;}

谁能告诉我为什么？（可以多加50分）。

[解决办法]
这里讲得挺清楚的
http://http://www.matrix67.com/blog/archives/115
[解决办法]
这玩意确实不好懂，一步步来，先弄懂那个next数组
[解决办法]
就是一个自动机
[解决办法]
两个版本的next实质是一样的，细节上的不同造成了答案不同
第一个版本的下标貌似是从0开始的，第二个实际上从1开始的

C/C++ code

void get_next2(){    int i = 0;    next2[0] = -1;    int j = -1;    while(i < len)    {        if(j == -1 || s[i] == s[j])        {            ++i;            ++j;            next2[i] = j;         //当while里面i=len-1时，这里的i就等于len了，越界        }        else            j = next2[j];    }}
[解决办法]
在学算法时， 尤其是学习初期编码能力不强时， 最主要的还是理解算法思想， 整天看代码也不见得好到那里去。

下面这两篇文章讲解的非常清楚：

http://www.matrix67.com/blog/archives/115
http://www.cppblog.com/goal00001111/archive/2009/05/10/82514.html
[解决办法]
http://blog.csdn.net/g_idea/archive/2009/09/04/4518410.aspx
[解决办法]
我也来凑凑热闹！

首先，传统的匹配算法，当主串与模式串出现不相等的情况下，往往需要回溯到主串开始位置的下一个位置上重新匹配。比如下图：
HTML code
      主串S    s1  s2  s3  s4  s5  s6  s7            s1  s2  s3  s4  s5  s6  s7      模式串P  p1  p2  p3  p4  p5           ->           p1  p2  p3  p4  p5
[解决办法]
主要是那个例子~~一定要 理解那个用已知信息来滑动 字串的原理 
 
[解决办法]
我就是看算法导论看透了.

感受就是:把那一章一字不落的看懂,你就懂了.

从霍纳法则递推的那个匹配算法,然后非常关键的状态机,状态机懂了KMP就幼稚了.
[解决办法]
百度百科 和 Wikipedia 都有分析，楼主可去看看，Wiki 里的例子举得恰到好处。
[解决办法]
就是模式匹配，建议楼主找点这方面的资料
[解决办法]
C/C++ code
/*    KMP算法主要是为了求解最大匹配的字符串及其长度  主要思想就是将已经匹配的字符串进行模式匹配。  这样比单个的比较的次数少一些。  author：macower  */  #include <iostream>   #include <string>   using namespace std;   int max = 0;   int loc = 0;   void KMP(string a ,string b);   int main()   {       string a;       string b;       while(cin>>a>>b)       {           KMP(a,b);              }       return 0;   }   void KMP(string a ,string b)   {       int lena = a.length();       int lenb = b.length();              int len = 1;       string tmpb;       string tmpa;       int max = 0;       int loc = 0;       for(int ij= 0;ij<=b.length()-max;ij++ )//判断最大长度 如果长度比max小就直接减枝       {           len = 1; //字符长度比较初始化为1           lenb = lenb-ij; //  需要比较b字串的长度       for(int ii = 0;ii<=lena-len;ii++)       {           if((len-1)>lenb) break; //如果查找的长度已经达剩余的总的长度则跳出循环           tmpb = b.substr(ij,len);//已经匹配的字符串           tmpa = a.substr(ii,len);           cout<<"tmpa = "<<tmpa<<"tmpb = "<<tmpb<<endl;           if(tmpa.compare(tmpb) == 0)            {               len++;                 if((max <(len-1))) //记录最大匹配长度max及其位置loc               {                   max = len-1;                   loc = ij;               }               ii--; //  确保指针不动与(int ii = 0;ii<=lena-len;ii++)的ii++相互抵消一保证从匹配继续向后移动           }                  }          }       cout<<"max=  "<<max <<endl;   }  本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/voyage_mh1987/archive/2010/07/15/5737293.aspx
[解决办法]
记住最简单的一点是：
在后缀中找前缀。 

 

查看更多 下一篇