LeetCode--459.重复的子字符串(字符串/KMP算法)

张开发
2026/4/11 23:05:57 15 分钟阅读

分享文章

LeetCode--459.重复的子字符串(字符串/KMP算法)
459.重复的子字符串题目描述给定一个非空的字符串s检查是否可以通过由它的一个子串重复多次构成。示例 1:输入: s abab 输出: true 解释: 可由子串 ab 重复两次构成。示例 2:输入: s aba 输出: false示例 3:输入: s abcabcabcabc 输出: true 解释: 可由子串 abc 重复四次构成。 (或子串 abcabc 重复两次构成。)提示1 s.length 104s由小写英文字母组成解题思路利用KMP算法找到与最长相等前后缀子串互补的子串代码classSolution{publicbooleanrepeatedSubstringPattern(Strings){intlens.length();int[]nextnewint[len];// 初始化intj0;next[0]j;for(inti1;ilen;i){// 最长前缀和最长后缀不匹配// 这里只关注第i个字符左侧字符串不包含i的前后缀while(j0s.charAt(i)!s.charAt(j)){// 回退jnext[j-1];}// 匹配成功if(s.charAt(i)s.charAt(j))j;next[i]j;}if(next[len-1]!0len%(len-next[len-1])0)returntrue;returnfalse;}}

更多文章