<svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg> <p>参考：代码随想录</p> 讯享网
KMP的主要思想:
当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
最长公共前后缀:
文章中字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
最长公共前后缀就是 前缀子串和后缀子串相同的最大长度。
ps：是子串
讯享网
为啥要把模式串（要匹配的串）逐个算出 最长公共前后缀 ：
因为你也不知道你匹配到哪就不能匹配了，将所有的情况列出来，然后哪里不能匹配直接对着表重新再弄。
a ：0
aa: a a 1
aab : aa ab 0后缀他必须包含最后一个字符 前缀必须包含最前面的那一个字符 所以相同的子串为0
aaba : a a 1
aabaa: aa aa2
aabaaf: 0
通过这个表格，哪里不匹配，去他前面那一格，找到最长公共前后缀，然后移动对应的格数。
怎么在代码中构建next数组:
讯享网
初始化：
定义两个指针i和j，j指向前缀末尾位置，i指向后缀末尾位置。
然后还要对next数组进行初始化赋值，如下：
处理前后缀相同的情况
如果 s[i] 与 s[j + 1] 相同，那么就同时向后移动i 和j 说明找到了相同的前后缀，同时还要将j（前缀的长度）赋给next[i], 因为next[i]要记录相同前后缀的长度。
代码如下：
讯享网
处理前后缀不相同的情况
如果 s[i] 与 s[j+1]不相同，也就是遇到 前后缀末尾不相同的情况，就要向前回退。
为什么用j=next[j]，就是相当于0-j+1这一段字符串匹配 i这一段字符串时，不匹配，于是用next数组来找到对应的
比如在adcadd这块，此时j=2，i=5，两个都+1，然后不相等了
不就相当于用adc来匹配adcadde吗，所以用adc的next数组
所以只要给定0，就可以一步一步的往上推整个。
回退必须j>=0,如果不是就代表无需回退。
当j>=0时,向前回退，也就是找到对应的s[i]==s[j+1]，单纯的j-1肯定不行，这样只算单个字符相等，前面的字符相不相等还不知道比如
比如这个枪口adc 匹配到add了，j–，此时d匹配上了d，但是ad 对的是add。
下面就是错误代码，可以去leetcode跑一下
讯享网
next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度。
那么 s[i] 与 s[j+1] 不相同，就要找 j+1前一个元素在next数组里的值（就是next[j]）。
错误解析：
“aabaaac”
aab 对应 aaa出问题了，所以用next数组回退，推到i=1，此时s[i]==s[j]，但是下面的代码却没有处理next[j]的情况
测试例题：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/138226.html