LeetCode459:重复子字符串的KMP算法解析

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/repeated-substring-pattern

题目要求：给定一个非空字符串，判断该字符串是否可以由其一个子串重复多次构成。输入字符串仅包含小写字母，长度不超过10000。

示例 1:

输入: “abab”

输出: True

解释: 可以由子字符串 “ab” 重复两次构成。

示例 2:

输入: “aba”

输出: False

示例 3:

输入: “abcabcabcabc”

输出: True

解释: 可以由子字符串 “abc” 重复四次构成（或子字符串 “abcabc” 重复两次构成）。

解题思路：

解决此问题的关键在于理解和运用KMP算法中的next数组。next数组记录了模式串中每个位置的最大公共前后缀长度减1。通过观察next数组的特点，我们可以发现，如果一个字符串可以由其子串重复构成，那么该字符串的next数组将展现出特定的规律。

如上图所示，首次出现的重复子串对应的next数组元素值为-1，而后续重复部分的next数组值逐渐增加。这是因为随着重复次数的增加，最大公共前后缀的长度也在增长。

图中红色和蓝色圈出的部分分别表示相同的最大前缀和后缀。设字符串长度为len，若(len - (next[len-1] + 1))能够整除len，则说明该字符串由重复子串构成。

以下是Java语言的实现代码：

class Solution { public boolean repeatedSubstringPattern(String s) { int[] next = getNext(s); int len = s.length(); if (next[len - 1] > 0 && len % (len - (next[len - 1] + 1)) == 0) return true; return false; } private int[] getNext(String s) { int j = -1; int[] next = new int[s.length()]; next[0] = j; for (int i = 1; i while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) j = next[j]; if (s.charAt(i) == s.charAt(j + 1)) j++; next[i] = j; } return next; } }