KMP算法--记录下来给自己看
KMP算法
突然发现有道云笔记的图片如果不开会员，不能手机在线看。所以发布在这里给自己看，各位看官如果有兴趣可以，点击去观看大佬的KMP算法解析视频，贼详细易懂
示例
字符串== T= abaacababcac
用来匹配的 P = ababc
算法分析
步骤1 得出字符串前缀
prefix table :p=ababc
- a
- ab
- aba
- abab
- ababc
步骤2 像这样得出最长前后缀
即从最后，和最前取有相同的子字符串
Table.png)]
最后的结果为
因为一般最长的不需要，所以最后的结果一般为
步骤3 开始匹配
- 当没有遇到匹配不上的时候，查询前缀表
2.再将字符串p移动到前缀表里的对应的数字对齐
如果是-1的位置，就是把前面的空格移到这里，不用匹配
代码分析
1. 最长对于前后缀的获取
其实如果后面的前后缀要相同的话，那么必须后面补的字符是前面的字符+1,列如
想要得到有两个最长前后缀字符子串，那么在前面必须有一个相同的基础上，前面的字符串的后一个字符必须与增加的那个字符相同