LeetCode--459.重复的子字符串（字符串/KMP算法）

459.重复的子字符串

题目描述

给定一个非空的字符串s，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba" 输出: false

示例 3:

输入: s = "abcabcabcabc" 输出: true 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

• 1 <= s.length <= 104
• s由小写英文字母组成

解题思路

利用KMP算法，找到与最长相等前后缀子串互补的子串：

代码

classSolution{publicbooleanrepeatedSubstringPattern(Strings){intlen=s.length();int[]next=newint[len];// 初始化intj=0;next[0]=j;for(inti=1;i<len;i++){// 最长前缀和最长后缀不匹配// 这里只关注第i个字符左侧字符串（不包含i）的前后缀while(j>0&&s.charAt(i)!=s.charAt(j)){// 回退j=next[j-1];}// 匹配成功if(s.charAt(i)==s.charAt(j))j++;next[i]=j;}if(next[len-1]!=0&&len%(len-next[len-1])==0)returntrue;returnfalse;}}