题目

题目来源：力扣（LeetCode）

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

示例 1:

输入: “abab”

输出: True

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

示例 2:

输入: “aba”

输出: False

示例 3:

输入: “abcabcabcabc”

输出: True

解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

思路分析

KMP算法

KMP算法中的next 数组记录的是最长相同前后缀的长度， 如果 next[len - 1] != -1，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。

最长相等前后缀的长度为：next[len - 1] + 1。

数组长度为：len。

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

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

字符串与next数组关系如下图：image.pngnext[len - 1] = 7，next[len - 1] + 1 = 8，8就是此时字符串asdfasdfasdf的最长相同前后缀的长度。

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

代码实现

前缀表统一减一的实现方式

  1. /**
  2.  * @param {string} s
  3.  * @return {boolean}
  4.  */
  6. var repeatedSubstringPattern = function (s) {
  7.   if (s.length == 0) {
  8.     return false;
  9.   }
  10.   let next = new Array(s.length);
  11.   getNext(next, s);
  12.   let len = s.length;
  13.   //  next[len - 1] != -1，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）
  14.   // 最长相等前后缀的长度为：next[len - 1] + 1
  15.   // len % (len - (next[len - 1] + 1)) == 0 ，则说明 (数组长度-最长相等前后缀的长度) 正好可以被 数组的长度整除，说明有该字符串有重复的子字符串
  17.   if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) {
  18.     return true;
  19.   }
  20.   return false;
  21. }
  24. function getNext(next, s) {
  25.   next[0] = -1;
  26.   let j = -1;
  27.   for (let i = 1; i < s.length; i++) { // 注意i从1开始
  28.     while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
  29.       j = next[j]; // 向前回溯
  30.     }
  31.     if (s[i] == s[j + 1]) { // 找到相同的前后缀
  32.       j++;
  33.     }
  34.     next[i] = j; // 将j（前缀的长度）赋给next[i]
  35.   }
  36. }

前缀表不减一的实现方式

  1. /**
  2.  * @param {string} s
  3.  * @return {boolean}
  4.  */
  6. var repeatedSubstringPattern = function (s) {
  7.   if (s.length == 0) {
  8.     return false;
  9.   }
  10.   let next = new Array(s.length);
  11.   getNext(next, s);
  12.   let len = s.length;
  13.   //  next[len - 1] != -1，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）
  14.   // 最长相等前后缀的长度为：next[len - 1] + 1
  15.   // len % (len - (next[len - 1] + 1)) == 0 ，则说明 (数组长度-最长相等前后缀的长度) 正好可以被 数组的长度整除，说明有该字符串有重复的子字符串
  17.   if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) {
  18.     return true;
  19.   }
  20.   return false;
  21. }
  24. function getNext(next, s) {
  25.   next[0] = 0;
  26.   let j = 0;
  27.   for (let i = 1; i < s.length; i++) { // 注意i从1开始
  28.     while (j > 0 && s[i] != s[j]) { // 前后缀不相同了
  29.       j = next[j - 1]; // 向前回溯
  30.     }
  31.     if (s[i] == s[j]) { // 找到相同的前后缀
  32.       j++;
  33.     }
  34.     next[i] = j; // 将j（前缀的长度）赋给next[i]
  35.   }
  36. }

参考阅读：
https://leetcode-cn.com/problems/repeated-substring-pattern/solution/dai-ma-sui-xiang-lu-dai-ni-gao-ding-zi-f-3mtx/