懂KMP算法的来啊~~
你想象一下在j=1时失配的情况就知道为什么会有这个条件了，j=1时只要失配就会让j回退到0，而模式串的0序列号处是没有字符元素的，0序列处存放的是模式串的长度，此时如果没有j==0这个判断条件，那么j的值永远没办法继续改变了，那就无法继续进行后面的匹配了 明白了没，这个在数据结构里还是算蛮不好懂的
看KMP算法中的next函数很多次了 始终不明白
求高手详细举例解释一下~~~~
这时老问题了，我以前做过一个文章是理解KMP，你留一个邮箱，你看看，不懂再问我。
算了我复制给你吧。
KMP算法一共分为两个部分，一个是失败函数，一个是快速查找函数(数据结构金远平版本)，KMP难度不在两个分开的函数，而是如果大家要合起来看，那的确难以接受，所以，我是分开理解的。
其中不乏很多小技巧，体现出程序的智慧。
首先，是失败函数。
失败函数的目的要明确：就是求出对于每个元素之前的首尾与之对应的最大真子串的子串个数(1.之所以是真，也是为了保证不进入死循环；2.求出个数，也就是说失败函数是int型数组)。
那怎么求出每个元素的对应的最大子串树呢
我们先来看看“人工”怎么求
例如：a b c a b c a c a b 那么，你就看看每个元素前面有没有与之匹配的元素，(我们将没有与之匹配的元素置为-1)最后发现0 1 2 3 4 5 6 7 8 9 a b c a b c a c a b -1 -1 -1 0 1 2 3 -1 0 1 那么我们人为理解了失败函数的功能，那么我们可以整理一下我们刚刚人工的思路：我们将当前元素与前面的元素比较
机器怎么做
存栈
impossible
那么机器理应看他前面那个元素的失败函数的值。
那么好啦，如果只看前面函数的值，那我再前面的元素施加的影响怎么考虑进去，那就出现了技巧1,巧用c＋＋指针解决，我们用两个指针，一个指针做数组的全局扫面，一个指针做内部的调整(纪录我里面连续的字符串)（能不能只用一个指针
不可能
）。
那么我们来看看失败函数的算法void String::Failed(){int LengthP = Length;f [ 0 ] = -1;\\\/\\\/初始化第一个元素，一定找不到，为“－1”for(int j = 0; j < LengthP; j ++){\\\/\\\/一个指针j,一直++int i = f [ j - 1 ];\\\/\\\/一个指针i,不停做调整while(*(str + j) != *(str + i + 1) && i >= 0)i = f [ i ];\\\/\\\/此处具体解释if (*(str + j) == *(str + i + 1))f [ j ] = i + 1;\\\/\\\/依然匹配，直接＋＋elsef [ j ] = -1;\\\/\\\/没有匹配，－1}}上面程序，最难懂的就是红色部分，道理何在
这里呢，不同的人有不同的说法，我仅以我的理解来讲，就是“匹配到死”
什么道理，就是说，一直找，找不到匹配就走人
比如以上面例子来说，如果遇到红色的c，那么根据我们刚刚分析的算法，先看他前面的元素，记下他失败函数的值（也就是i，i就是跟他匹配的最大字串的地址，这里为3）,那么*(str ＋ j)是c，那么*(str + i + 1)就是第4个元素为b，显然不匹配，那么下一步i ＝
，i ＝ 0，到这里，或许你和我有一样的疑问
不成功那么按人脑应该想到是看看第一个元素
或是再看看前面几个元素与后面几个元素一样不一样
几个
别开玩笑了，计算机会杀了你，它只能看一个
那么看哪个
这里的技巧我实在是不能多说
太NB啦
他利用了失败函数的递归效应，运用其内部结构制约这段太长，一定要分段啊。
也就是说，我第一个匹配的字符串是蓝色的b，那么不等，我下一次看的是谁
是b的最大子串的位置也就是绿色的b,那么好啦，这个例子还不能说明什么，以下均为假设（也可以比如d c b d d c b d c）：如果我的红色正好和绿色相等，不是“好像”少看了一位，那就是，你怎么能保证绿色前面那位与我的红色前面一位相等
那么这里就是技巧2, 因为我每次找都是找的子串，那么我一定能保证相等（也就是 红c前面的一定等于蓝d前面的d也等于绿c前面的d）。
ok，到这里，不知大家的感觉是更清楚还是在心理狂骂我。
接下来就是较为简单的快速查找，利用了失败函数的快速查找，效率什么也自然就高了。
以下是程序:int String::FastFinding(String *pat){int j = 0, i = 0;\\\/\\\/ 申请两个指针，分别扫描模版字符串和目标串int LengthP = pat.Length, LengthS = Length;while( j < LengthP && i < LengthS )if( pat.str[ j ] == str[ i ])i ++;j ++;\\\/\\\/相等，都好说elseif(j == 0) i ++;\\\/\\\/ 不等，而且j刚好才扫到第一个else j = pat.f[ j-1 ] + 1;\\\/\\\/详细讲if( j < LengthP || LengthP == 0) return -1;\\\/\\\/没有找到else return i - LengthP;\\\/\\\/找到了}这段代码的难点也是红色子部分，这部分是说没有匹配，那么模版串要怎么移动，熟悉“蛮力匹配”算法的都清楚，他要回朔，就是模版串要走回头路，那么我KMP算法就是要尽量少走回头路，你可以把问题相成两把尺子，一把大尺子和一把小尺子，那么蛮力匹配就是每次小尺子只移动一格，每次i＋＋，那么KMP是每次平均可以移动很多格（最好是没有匹配的，也就是j ＝ 0,那么每次都是大踏步前进
）（这里要大家理解了，这个是动态图，我懒的做了）所以他好
其余，KMP的时间复杂度，正确性我就不多谈了，这些我们不care
那么到这里，KMP算法也算是讲完了，我觉得又理解了一遍，不错不错
你要电子版就留邮箱
如何更好的理解和掌握kmp算法
问题给你解决了#include stdio.h#include string.hmain(){ char t[]=ababcabc; int i=1,j=0,k=1,next[8]; for(i=0;i<8;i++){next[i]=0;} next[0]=0;next[1]=1; i=1;\\\/\\\/这里的i一定要重新赋值 因为上面的循环你用到了i 循环结束后 i的值变为8 而下面while循环的条件是i<8 所以循环一次都没有执行 当然是初值了 while(i<8){ if(j==0||t[i]==t[j]){++i;++j;next[i]=j;} else{j=next[j];} } printf(next[0]=0\\\); for(k=1;k<8;k++)\\\/\\\/注意这里的循环 k=1不能省略 {printf(next[%d]=%d\\\,k,next[k]);k++;}}
用KMP算法写的完整程序，麻烦您了
自己写的测试了几个结果是对的性能没有好的数据测试仅供参考，主要靠你自己\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/c++\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/#include 算法3.5——KMP算法 1. 在串S和串T中分别设比较的起始下标i和j； 2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕 2.1 如果S[i]=T[j]，则继续比较S和T的下一个字符；否则 2.2 将j向右滑动到next[j]位置，即j=next[j]； 2.3 如果j=0，则将i和j分别加1，准备下一趟比较； 3. 如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回0；void GetNext(char T[ ], int next[ ]){ next[1]=0; j=1; k=0; while (j急~求KMP算法
