题目
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
示例 2:
输入: s = "aba"
输出: false
示例 3:
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
个人解答（前缀表不减1）
class Solution {
public boolean repeatedSubstringPattern(String s) {
if (s.length() == 0) {
return false;
}
int[] next = new int[s.length()];
int len = s.length();
//获取模式串的前缀表
getNext(next,s);
// 最后判断是否是重复的子字符串，这里 next[len-1] 即代表next数组末尾的值。
//这里len - next[len-1])就是一个周期的长度。
//如果整个长度能整除周期长度，那么说明是重复的子串构成的。
if (next[len-1] > 0 && len % (len - next[len-1]) == 0) {
return true;
}
return false;
}
//确定前缀表的每一个数值
private void getNext(int[] next, String s) {
int j = 0;
next[0] = 0;
for (int i = 1; i < s.length(); i++) {
while (j > 0 && s.charAt(j) != s.charAt(i))
j = next[j - 1];
if (s.charAt(j) == s.charAt(i))
j++;
next[i] = j;
}
}
}
个人总结
第一次看到这个题目实在carl哥的代码随想录里面，第一次看KMP算法的文字解释根本看不懂，后面看了b站上carl哥的视频才对前缀表以及前缀表的作用有了那么一丢丢感觉！！做了两道题之后，总结出如下规律：
1.KMP算法用于字符串匹配上，也就是说出现字符串匹配就可以想到KMP算法
2.KMP实现的步骤
先构造一个方法getNext(int[] next,String s),设置next数组的每一个元素
然后写匹配过程(有无此过程看实际情况)，先找到第一次匹配的位置，用while语句，里面语句是j=next[j-1];
跳出while语句后，再做判断，如果匹配，那么j后移动；
最后根据不同需求做不同的判断，按需求返回不同的值。
总之KMP算法真的太难了！！我被折磨的不轻，真佩服Knuth,Morris,Pratt三位大佬!
不多说了，好好学习吧!!