kmp算法代码讲解（KMP算法还能干这个）
kmp算法代码讲解（KMP算法还能干这个）那么寻找重复子串怎么也涉及到KMP算法了呢？我们在字符串：都来看看KMP的看家本领！里提到了，在一个串中查找是否出现过另一个串，这是KMP的看家本领。示例 2:输入: "aba"输出: False示例 3:输入: "abcabcabcabc"输出: True解释: 可由子字符串 "abc" 重复四次构成。(或者子字符串 "abcabc" 重复两次构成。)这又是一道标准的KMP的题目。
不瞒你说，重复子串问题，KMP很拿手
❞
题目459.重复的子字符串给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
输入: "aba"
输出: False
示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。(或者子字符串 "abcabc" 重复两次构成。)
这又是一道标准的KMP的题目。
我们在字符串：都来看看KMP的看家本领！里提到了，在一个串中查找是否出现过另一个串，这是KMP的看家本领。
那么寻找重复子串怎么也涉及到KMP算法了呢？
这里就要说一说next数组了，next 数组记录的就是最长相同前后缀( 字符串：听说你对KMP有这些疑问？ 这里介绍了什么是前缀，什么是后缀，什么又是最长相同前后缀)， 如果 next[len - 1] != -1，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。
最长相等前后缀的长度为：next[len - 1] 1。
数组长度为：len。
如果len % (len - (next[len - 1] 1)) == 0 ，则说明 (数组长度-最长相等前后缀的长度) 正好可以被 数组的长度整除，说明有该字符串有重复的子字符串。
「强烈建议大家把next数组打印出来，看看next数组里的规律，有助于理解KMP算法」
如图：
此时next[len - 1] = 7，next[len - 1] 1 = 8，8就是此时 字符串asdfasdfasdf的最长相同前后缀的长度。
(len - (next[len - 1] 1)) 也就是：12(字符串的长度) - 8(最长公共前后缀的长度) = 4， 4正好可以被 12(字符串的长度) 整除，所以说明有重复的子字符串（asdf）。
代码如下：
C 代码classSolution{
public:
// KMP里标准构建next数组的过程
voidgetNext(int*next conststring&s){
next[0]=-1;
intj=-1;
for(inti=1;i<s.size();i ){
while(j>=0&&s[i]!=s[j 1]){
j=next[j];
}
if(s[i]==s[j 1]){
j ;
}
next[i]=j;
}
}
boolrepeatedSubstringPattern(strings){
if(s.size()==0){
returnfalse;
}
intnext[s.size()];
getNext(next s);
intlen=s.size();
if(next[len-1]!=-1&&len%(len-(next[len-1] 1))==0){
returntrue;
}
returnfalse;
}
};
拓展
此时我们已经分享了三篇KMP的文章，首先是字符串：字符串：KMP是时候上场了（一文读懂系列） 讲解KMP算法的基础理论，给出next数组究竟是如何来了，前缀表又是怎么回事，为什么要选择前缀表。
然后通过字符串：字符串：都来看看KMP算法的看家本领 讲解一道KMP的经典题目，判断文本串里是否出现过模式串，这里涉及到构造next数组的代码实现，以及使用next数组完成模式串与文本串的匹配过程。
后来很多同学反馈说：搞不懂前后缀，什么又是最长相同前后缀（最长公共前后缀我认为这个用词不准确），以及为什么前缀表要统一减一（右移）呢，不减一行不行？针对这些问题，我在字符串：听说你对KMP还有这些疑问？ 中又给出了详细的讲解。
在留言区留下你的思路吧！
-------end-------
我将算法学习相关的资料已经整理到了
Github ：https://github.com/youngyangyang04/leetcode-master，里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图看一看一定会有所收获！
我是程序员Carl，哈工大师兄，先后在腾讯和百度打杂，这里每天8:35准时推送一道经典算法题目，我选择的每道题目都不是孤立的，而是由浅入深，环环相扣，帮你梳理算法知识脉络，轻松学算法！
每天8:35准时推送一道经典算法题目，推送的每道题目都不是孤立的，而是由浅入深，环环相扣，帮你梳理算法知识脉络，轻松学算法！
@代码随想录期待你的关注
