java数据结构与算法刷题-----LeetCode459. 重复的子字符串

本文主要是介绍java数据结构与算法刷题-----LeetCode459. 重复的子字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846

本题的高效解法，需要使用KMP算法中，NEXT数组的处理逻辑

KMP算法https://blog.csdn.net/grd_java/article/details/136107363

解题思路

1. 以abcabcabcabc为例对应NEXT数组为[0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
2. 可见最长公共前后缀为abcabcabc.我们发现，如果是通过固定子串重复若干次组成的字符串，减去最长公共前后缀后，剩下的就是这个重复若干次的固定子串
3. 所以我们可以利用KMP算法中的NEXT数组，获取整个字符串的最长公共前后缀长度。
4. 对于这个例子就可以得到最长公共前后缀长度为9. 而整个字符串长度len = 12. 12-9 = 3. 3就是固定重复子串abc的长度。
5. 如果整个字符串都可以被abc这个固定重复子串整除，那么就说明这个字符串一定是满足题意的。
6. 也就是len % (len - next[len-1]) == 0的话，就满足题意。简单来说就是len - next[len-1]是固定重复子串abc的长度。len是整个字符串的长度。如果len可以被abc这个固定重复子串整除，那么就满足题意。

代码

class Solution {public boolean repeatedSubstringPattern(String s) {if (s.equals("")) return false;int len = s.length();//字符串长度char[] chars = s.toCharArray();//转换为字符数组int[] next = new int[len];//创建KMP算法的NEXT数组，下标从1开始//KMP--NEXT数组三步走for (int i = 1, j = 0; i < len; i++) {//直接从第二个元素比while (j > 0 && chars[i] != chars[j]) j = next[j-1];//如果不匹配，获取应该回退的位置if (chars[i] == chars[j]) j++;//如果匹配，则公共缀长度+1next[i] = j;//记录当前缀的公共前后缀长度}//此时next[len-1]保存的是整个字符串的最长公共前后缀长度。//如果此时next[len-1]这个前后缀公共长度，将其从字符串中剔除，正好剩下重复子串//那就说明整个字符串都是用重复子串构成的。整个字符串的长度，也就可以通过这个重复子串整除if (next[len-1] > 0 && len % (len - next[len-1]) == 0) return true;//如果可以被重复子串长度整除就返回trueelse return false;//否则返回false}
}

这篇关于java数据结构与算法刷题-----LeetCode459. 重复的子字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---