0459.重复的子字符串 - 图1
参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

KMP算法还能干这个

459.重复的子字符串

力扣题目链接

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:
输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成。

示例 2:
输入: “aba”
输出: False

示例 3:
输入: “abcabcabcabc”
输出: True
解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

思路

这又是一道标准的KMP的题目。

如果KMP还不够了解，可以看我的B站：

我们在字符串：KMP算法精讲里提到了，在一个串中查找是否出现过另一个串，这是KMP的看家本领。

那么寻找重复子串怎么也涉及到KMP算法了呢？

这里就要说一说next数组了，next 数组记录的就是最长相同前后缀( 字符串：KMP算法精讲 这里介绍了什么是前缀，什么是后缀，什么又是最长相同前后缀)， 如果 next[len - 1] != -1，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。

最长相等前后缀的长度为：next[len - 1] + 1。(这里的next数组是以统一减一的方式计算的，因此需要+1)

数组长度为：len。

如果len % (len - (next[len - 1] + 1)) == 0 ，则说明 (数组长度-最长相等前后缀的长度) 正好可以被 数组的长度整除，说明有该字符串有重复的子字符串。

数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。

强烈建议大家把next数组打印出来，看看next数组里的规律，有助于理解KMP算法

如图：

0459.重复的子字符串 - 图2

next[len - 1] = 7，next[len - 1] + 1 = 8，8就是此时字符串asdfasdfasdf的最长相同前后缀的长度。

(len - (next[len - 1] + 1)) 也就是： 12(字符串的长度) - 8(最长公共前后缀的长度) = 4， 4正好可以被 12(字符串的长度) 整除，所以说明有重复的子字符串（asdf）。

C++代码如下：（这里使用了前缀表统一减一的实现方式）

  1. class Solution {
  2. public:
  3.     void getNext (int* next, const string& s){
  4.         next[0] = -1;
  5.         int j = -1;
  6.         for(int i = 1;i < s.size(); i++){
  7.             while(j >= 0 && s[i] != s[j+1]) {
  8.                 j = next[j];
  9.             }
  10.             if(s[i] == s[j+1]) {
  11.                 j++;
  12.             }
  13.             next[i] = j;
  14.         }
  15.     }
  16.     bool repeatedSubstringPattern (string s) {
  17.         if (s.size() == 0) {
  18.             return false;
  19.         }
  20.         int next[s.size()];
  21.         getNext(next, s);
  22.         int len = s.size();
  23.         if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) {
  24.             return true;
  25.         }
  26.         return false;
  27.     }
  28. };

前缀表（不减一）的C++代码实现

  1. class Solution {
  2. public:
  3.     void getNext (int* next, const string& s){
  4.         next[0] = 0;
  5.         int j = 0;
  6.         for(int i = 1;i < s.size(); i++){
  7.             while(j > 0 && s[i] != s[j]) {
  8.                 j = next[j - 1];
  9.             }
  10.             if(s[i] == s[j]) {
  11.                 j++;
  12.             }
  13.             next[i] = j;
  14.         }
  15.     }
  16.     bool repeatedSubstringPattern (string s) {
  17.         if (s.size() == 0) {
  18.             return false;
  19.         }
  20.         int next[s.size()];
  21.         getNext(next, s);
  22.         int len = s.size();
  23.         if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
  24.             return true;
  25.         }
  26.         return false;
  27.     }
  28. };

拓展

在字符串：KMP算法精讲中讲解KMP算法的基础理论，给出next数组究竟是如何来了，前缀表又是怎么回事，为什么要选择前缀表。

讲解一道KMP的经典题目，力扣：28. 实现 strStr()，判断文本串里是否出现过模式串，这里涉及到构造next数组的代码实现，以及使用next数组完成模式串与文本串的匹配过程。

后来很多同学反馈说：搞不懂前后缀，什么又是最长相同前后缀（最长公共前后缀我认为这个用词不准确），以及为什么前缀表要统一减一（右移）呢，不减一行不行？针对这些问题，我在字符串：KMP算法精讲给出了详细的讲解。

其他语言版本

Java：

  1. class Solution {
  2.     public boolean repeatedSubstringPattern(String s) {
  3.         if (s.equals("")) return false;
  5.         int len = s.length();
  6.         // 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了
  7.         s = " " + s;
  8.         char[] chars = s.toCharArray();
  9.         int[] next = new int[len + 1];
  11.         // 构造 next 数组过程，j从0开始(空格)，i从2开始
  12.         for (int i = 2, j = 0; i <= len; i++) {
  13.             // 匹配不成功，j回到前一位置 next 数组所对应的值
  14.             while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
  15.             // 匹配成功，j往后移
  16.             if (chars[i] == chars[j + 1]) j++;
  17.             // 更新 next 数组的值
  18.             next[i] = j;
  19.         }
  21.         // 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
  22.         if (next[len] > 0 && len % (len - next[len]) == 0) {
  23.             return true;
  24.         }
  25.         return false;
  26.     }
  27. }

Python：

这里使用了前缀表统一减一的实现方式

  1. class Solution:
  2.     def repeatedSubstringPattern(self, s: str) -> bool:  
  3.         if len(s) == 0:
  4.             return False
  5.         nxt = [0] * len(s)
  6.         self.getNext(nxt, s)
  7.         if nxt[-1] != -1 and len(s) % (len(s) - (nxt[-1] + 1)) == 0:
  8.             return True
  9.         return False
  11.     def getNext(self, nxt, s):
  12.         nxt[0] = -1
  13.         j = -1
  14.         for i in range(1, len(s)):
  15.             while j >= 0 and s[i] != s[j+1]:
  16.                 j = nxt[j]
  17.             if s[i] == s[j+1]:
  18.                 j += 1
  19.             nxt[i] = j
  20.         return nxt

前缀表（不减一）的代码实现

  1. class Solution:
  2.     def repeatedSubstringPattern(self, s: str) -> bool:  
  3.         if len(s) == 0:
  4.             return False
  5.         nxt = [0] * len(s)
  6.         self.getNext(nxt, s)
  7.         if nxt[-1] != 0 and len(s) % (len(s) - nxt[-1]) == 0:
  8.             return True
  9.         return False
  11.     def getNext(self, nxt, s):
  12.         nxt[0] = 0
  13.         j = 0
  14.         for i in range(1, len(s)):
  15.             while j > 0 and s[i] != s[j]:
  16.                 j = nxt[j - 1]
  17.             if s[i] == s[j]:
  18.                 j += 1
  19.             nxt[i] = j
  20.         return nxt

Go：

这里使用了前缀表统一减一的实现方式

  1. func repeatedSubstringPattern(s string) bool {
  2.     n := len(s)
  3.     if n == 0 {
  4.         return false
  5.     }
  6.     next := make([]int, n)
  7.     j := -1
  8.     next[0] = j
  9.     for i := 1; i < n; i++ {
  10.         for j >= 0 && s[i] != s[j+1] {
  11.             j = next[j]
  12.         }
  13.         if s[i] == s[j+1] {
  14.             j++
  15.         }
  16.         next[i] = j
  17.     }
  18.     // next[n-1]+1 最长相同前后缀的长度
  19.     if next[n-1] != -1 && n%(n-(next[n-1]+1)) == 0 {
  20.         return true
  21.     }
  22.     return false
  23. }

前缀表（不减一）的代码实现

  1. func repeatedSubstringPattern(s string) bool {
  2.     n := len(s)
  3.     if n == 0 {
  4.         return false
  5.     }
  6.     j := 0
  7.     next := make([]int, n)
  8.     next[0] = j
  9.     for i := 1; i < n; i++ {
  10.         for j > 0 && s[i] != s[j] {
  11.             j = next[j-1]
  12.         }
  13.         if s[i] == s[j] {
  14.             j++
  15.         }
  16.         next[i] = j
  17.     }
  18.     // next[n-1]  最长相同前后缀的长度
  19.     if next[n-1] != 0 && n%(n-next[n-1]) == 0 {
  20.         return true
  21.     }
  22.     return false
  23. }

JavaScript版本

前缀表统一减一

  1. /**
  2.  * @param {string} s
  3.  * @return {boolean}
  4.  */
  5. var repeatedSubstringPattern = function (s) {
  6.     if (s.length === 0)
  7.         return false;
  9.     const getNext = (s) => {
  10.         let next = [];
  11.         let j = -1;
  13.         next.push(j);
  15.         for (let i = 1; i < s.length; ++i) {
  16.             while (j >= 0 && s[i] !== s[j + 1])
  17.                 j = next[j];
  18.             if (s[i] === s[j + 1])
  19.                 j++;
  20.             next.push(j);
  21.         }
  23.         return next;
  24.     }
  26.     let next = getNext(s);
  28.     if (next[next.length - 1] !== -1 && s.length % (s.length - (next[next.length - 1] + 1)) === 0)
  29.         return true;
  30.     return false;
  31. };

前缀表统一不减一

  1. /**
  2.  * @param {string} s
  3.  * @return {boolean}
  4.  */
  5. var repeatedSubstringPattern = function (s) {
  6.     if (s.length === 0)
  7.         return false;
  9.     const getNext = (s) => {
  10.         let next = [];
  11.         let j = 0;
  13.         next.push(j);
  15.         for (let i = 1; i < s.length; ++i) {
  16.             while (j > 0 && s[i] !== s[j])
  17.                 j = next[j - 1];
  18.             if (s[i] === s[j])
  19.                 j++;
  20.             next.push(j);
  21.         }
  23.         return next;
  24.     }
  26.     let next = getNext(s);
  28.     if (next[next.length - 1] !== 0 && s.length % (s.length - next[next.length - 1]) === 0)
  29.         return true;
  30.     return false;
  31. };

TypeScript:

前缀表统一减一

  1. function repeatedSubstringPattern(s: string): boolean {
  2.     function getNext(str: string): number[] {
  3.         let next: number[] = [];
  4.         let j: number = -1;
  5.         next[0] = j;
  6.         for (let i = 1, length = str.length; i < length; i++) {
  7.             while (j >= 0 && str[i] !== str[j + 1]) {
  8.                 j = next[j];
  9.             }
  10.             if (str[i] === str[j + 1]) {
  11.                 j++;
  12.             }
  13.             next[i] = j;
  14.         }
  15.         return next;
  16.     }
  18.     let next: number[] = getNext(s);
  19.     let sLength: number = s.length;
  20.     let nextLength: number = next.length;
  21.     let suffixLength: number = next[nextLength - 1] + 1;
  22.     if (suffixLength > 0 && sLength % (sLength - suffixLength) === 0) return true;
  23.     return false;
  24. };

前缀表不减一

  1. function repeatedSubstringPattern(s: string): boolean {
  2.     function getNext(str: string): number[] {
  3.         let next: number[] = [];
  4.         let j: number = 0;
  5.         next[0] = j;
  6.         for (let i = 1, length = str.length; i < length; i++) {
  7.             while (j > 0 && str[i] !== str[j]) {
  8.                 j = next[j - 1];
  9.             }
  10.             if (str[i] === str[j]) {
  11.                 j++;
  12.             }
  13.             next[i] = j;
  14.         }
  15.         return next;
  16.     }
  18.     let next: number[] = getNext(s);
  19.     let sLength: number = s.length;
  20.     let nextLength: number = next.length;
  21.     let suffixLength: number = next[nextLength - 1];
  22.     if (suffixLength > 0 && sLength % (sLength - suffixLength) === 0) return true;
  23.     return false;
  24. };

0459.重复的子字符串 - 图3