关于KMP算法个人理解
笔者经过一个下午的整理，基本走通了所有逻辑。至于代码就不贴上了，功底有点烂。思路通了大于一切 代码怎么都能挤出来的
有如下一组字符串
A：abcdabcxabcd
B：abcxabcd
需要做的事 就是在A中寻找有没有B字符串
第一个要理解的点，B字符串需要首先自我匹配是否有相同的前缀后缀
B: a b c x a b c d
0 1 2 3 4 5 6 7
构建next数组 0 0 0 0 1 2 3 0
关于这个next数组怎么得来，有变量 i j ,i代表B数组下标0，j代表B数组1（从1开始）进行匹配
index[0] = 0,这是初始值
取i=0 对应的字符串 a 与j=1对应的字符串b 比较，此时不相同 j++,数组next赋值 index[1] = 0;
取i=0 对应的字符串 a 与j=2对应的字符串c 比较，此时不相同 j++,数组next赋值 index[2] = 0;
取i=0 对应的字符串 a 与j=3对应的字符串x 比较，此时不相同 j++,数组next赋值 index[3] = 0;
取i=0 对应的字符串 a 与j=4对应的字符串a 比较，此时结果相同,则i++,且j++,并且next赋值index[4] = 1 ,意思是相同的话就+1;
（注释：这里是，相同的情况，会写入i+1的值，此时i = 0 所以+1 ）
取i=1 对应的字符串 b 与 j = 5对应的字符串b比较，此时结果相同,,则i++,且j++,并且next赋值index[5] = 2 ,意思是相同的话就+1;
（注释：这里是，相同的情况，会写入i+1的值，此时i = 1 所以+1 ）
取i=2 对应的字符串 c 与 j = 6对应的字符串c比较，此时结果相同,,则i++,且j++,并且next赋值index[6] = 3 ,意思是相同的话就+1;
（注释：这里是，相同的情况，会写入i+1的值，此时i = 2 所以+1 ）
特殊情况来了
取i = 3对应的字符串x 与 j =7对应的字符串d比较，此时结果不同，那么i取前面（i--）取2对应的字符串c还是不同，再取
i-- 取1不同 会发现没有相同的，此时整个组没有与d相同的字符串，则赋值i=0并且填入index[7] = 0;
和上面一样的数组，有点太长了 所以直接拿下来
B: a b c x a b c d
0 1 2 3 4 5 6 7
构建next数组 0 0 0 0 1 2 3 0
拿到了3 意思就是这个数组最大的相同前缀是123 对应的也就是abc
再回到我们的字符串来
A：a b c d a b c x a b c f a b c x a b c x a b c d i
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
B：a b c x a b c d j (next: 0 0 0 0 1 2 3 0 )
0 1 2 3 4 5 6 7
进行第一次匹配 会发现在i=3并且j=3的时候字符串不匹配 触发重新匹配方法
此时查询在next的数组下标-1里面对应的值为0，所以j 又回到0 并且i从i+1 从i=4开始匹配
第二次匹配开始，i = 4 i = 5 i = 6 i =7 ......一直到 i = 11不匹配,
此时j = 7 -1 查到对应的值为next【index】 = 3 ,所以可以肯定的是，3前面的字符串肯定都包含 所以只需要在b里面的next =3 开始查找就Ok
此时 需要匹配的值为next下标为3的值为x 取出来 x与 i = 11比较，为f 还是不匹配（这样就避免回到b字符串的头部了，）
但是这里还是不匹配，此时取next-1的值 为0 又开始从0开始（回到子串的头部，因为被F打断了）
开始第三次匹配，此时一直到 i = 18 并且 j =7 出现不匹配情况，此时J-1=6 取c 与 i =18 比较，是C，则直接继续往下开始匹配x a b cd
最后这种情况是因为取出来的值和相对应的比较的值相等 所以才继续匹配（因为取出来的值是有相同前缀的，i = 18的c 前面是肯定包含了abc的）此时对应的next数组值为3，直接开始从B字符串的下标为3的值X开始匹配，与i = 19匹配 是匹配的话就继续匹配 不匹配 则从0开始。
好了kmp的算法和规则到此结束。(避免了会从B字符串从头开始，一旦碰到相同前缀的时候)
网友评论