KMP算法学习

前言

上个学期学了一下KMP，基本上都忘光了，因为没有完全理解透彻。

学算法还是要理解清楚的，所以这次我又通彻地学习了一下KMP算法。

这篇博客以推荐文章为主，我自己的见解比较少（因为我太懒了）。

Blog推荐

KMP ----从入门到理解到彻底理解

自己的总结

KMP其实也不难，就两个过程

（S[ ]是文本串，就是长的字符串，T[ ]是短的单词）

1. 匹配 ：当匹配字符失效 ，即\(S[ i ] != T[ j ]\) , 那么 \(j\) 指针指向 \(next[ j ]\) , 即 \(j = next[ j ]\)

2. 求next：\(next[ j ]\) 就是单词\(T[ 0 ~ j-1 ]\) 的最长相同前后缀 如 ABQQABK 当指针 \(j\) 指到 ' K ' 位置 \(T[ 0 ~ j-1 ]\) 就是 " ABQQAB " 这一串， 显然这一串的前面和后面都有AB，所以当前的next就为2( 字符串从零开始，2位置是Q ，Q前面的前缀相等，这时候比较Q和S[ i ])

next数组利用递推求解，我在这里不想讲了（懒）

祝你学会KMP！