先说一下为啥要了解kmp算法，因为阿里面试有道面试题目，如果在所有字符串最快速度找出目标字符串的位置。我用了最暴力算法，即：
被查找字符串和目标字符串比较的时候，当匹配到目标字符串的第一个字符的时候，若中间一个字符不匹配的话，则被查找字符串和目标字符串都需要重新回溯。如下，时间复杂度自然是M * N
a b c d a b e f g h p b c d b h (M个)
b c d f (f找不到) (N个)
b c d f (重新回溯)
下面引入到KMP算法，例如： 搜索关键词 ABCDABD ，目标串 BBC ABCDAB ABCDABCDABDE
1 首先找出关键词ABCDABD的特征，也就是如何找出它的部分匹配值:
前缀 后缀 公共子串的长度
A x x 0
AB A B 0
ABC AB A BC C 0
ABCD ABC AB A BCD D CD 0
ABCDA ABCD ABC AB A A DA CDA BCDA 1
ABCDAB ABCDA ABCD B AB DAB CDAB 2
ABC AB A BCDAB
ABCDABD A AB ABC ABCD D BD ABD DABD CDABD 0
ABCDA ABCDAB BCDABD
即关键词每个字母的匹配值，如下
2 寻找字符串的位置
步骤1 (斜线部分表示不匹配):
(1) BBC ABCDAB ABCDABCDABDE
ABCDABD
(2)BBC ABCDAB ABCDABCDABDE
ABCDABD
(3)BBC ABCDAB ABCDABCDABDE
ABCDABD
(4)BBC ABCDAB ABCDABCDABDE
ABCDABD
(5)BBC ABCDAB ABCDABCDABDE
ABCDABD
步骤1中(5) D与空格不匹配，若按以前暴力的方式，则从上一次开始匹配的第一字符的下一个字符开始重新比较，效率比较低了，现在就按如下原则开始移动：
移动的位数 = 已匹配的字符数 - 关键词匹配的最后一个词的匹配值
步骤2
(1) 则搜索关键词移动的位数 = 6(已经匹配 ABCDAB) - 2(最后一个值的匹配值为2) ，所以移动结果如下:
BBC ABCDAB ABCDABCDABDE
ABCDABD
(2) 以上比较C与空格不匹配，则移动的位数 = 2 (已经匹配的数目)- 0(最后一个匹配字符B的值) = 2
BBC ABCDAB ABCDABCDABDE
ABCDABD
(3) 按步骤1的方式进行匹配
BBC ABCDAB ABCDABCDABDE
ABCDABD
(4) 需要移动的位置 ，移动的位数 = 6 - 2 = 4
BBC ABCDAB ABCDABCDABDE
ABCDABD
以上是kmp算法详解，比较简单，算是了解算法了，但是还得深究原理。也就是达到学习的what,how,但没有知道why，所以下一篇会更新why
