题目描述
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
示例 2:
输入: s = "aba"
输出: false
示例 3:
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
提示：
1 <= s.length <= 104s由小写英文字母组成
分析解答
重复的子串连接成父串？重复？repeat！重复的次数？父串的长度是子串的几倍就是重复几次！
/**
* @param {string} s
* @return {boolean}
*/
var repeatedSubstringPattern = function (s) {
let subStr = ''
for (let i = 0; i < s.length - 1; i++) {
subStr += s[i]
if (s === subStr.repeat(Math.floor(s.length / subStr.length))) {
return true
}
}
return false
};
思路拓展
移动匹配
既然是由重复的子串构成的，那么该字符串的首尾子串一定是相等的。所以：首 + 中间部分 + 尾 => 原字符串，那么，以此类推，尾 + 中间部分 + 首 => 原字符串。
所以我们的思路是：将两个字符串拼起来，找这个二倍的字符串是否含有原字符串(去掉首尾，防止两个原字符串的干扰)。
var repeatedSubstringPattern = function (s) {
let str = s + s
str = str.slice(1, str.length - 1)
if (str.includes(s)) {
return true
}
return false
};
KMP
next 数组是一个辅助数组，用来记录每个位置之前的最长相同前缀后缀的长度。通过计算next数组，就能得到字符串中最长的重复子串的长度。
主要逻辑如下：
- 首先进行一些边界判断，如果字符串的长度为0，则返回false。
- 然后定义了一个名为getNext的函数，用来计算next数组。这个函数通过使用双指针遍历字符串，根据不同的情况更新指针及next数组的值。具体来说：
- 初始化一个next数组和一个指针j。
- 将j的初始值0存入next数组中。
- 从1到字符串的长度-1进行遍历，将指针j根据不同情况进行更新，并将更新后的j的值存入next数组中。
- 最后返回next数组。
- 接下来，调用getNext函数得到next数组。
- 最后通过判断条件(最后位置的最长相同前后缀不能为 0 ；而且整个字符串的长度一定是最长相同前后缀的整数倍，也就是模为 0)来比较字符串长度是否是最长重复子串长度的倍数，如果是则返回true，否则返回false。
这段代码主要运用了KMP算法中的next数组计算来判断字符串是否由重复的子串组成。
/**
* @param {string} s
* @return {boolean}
*/
var repeatedSubstringPattern = function (s) {
if (s.length === 0) {
return false
}
const getNext = (s) => {
let next = []
let j = 0
next.push(j)
for (let i = 1; i < s.length; i++) {
while (j > 0 && s[i] !== s[j]) {
j = next[j - 1]
}
if (s[i] === s[j]) {
j++
}
next.push(j)
}
return next
}
let next = getNext(s)
if (next[next.length - 1] !== 0 && s.length % (s.length - next[next.length - 1]) === 0) {
return true
}
return false
};
let s = "aba"
console.log(repeatedSubstringPattern(s))
详细讲讲 getNext 这个方法：
当进行字符串匹配时，我们需要找到一个最长的相同前缀后缀。这个相同前缀后缀的长度决定了我们在匹配失败时应该回退多少位。
getNext方法就是用来计算这个最长的相同前缀后缀的长度。它使用了双指针的方法来遍历字符串s，并根据不同的情况更新指针和next数组的值。
具体的实现逻辑如下：
- 首先，我们先定义一个数组next用来存储最长相同前缀后缀的长度。
- 接着，我们定义两个指针i和j，初始值都为0。指针i表示当前要计算最长相同前缀后缀的后缀的末尾位置，指针j表示当前已经求得的最长相同前缀后缀的长度。
- 先将指针j的初始值0存入next数组的第一个位置。
- 从字符串s的第二个字符开始，即i从1到s.length-1，进行遍历。
- 在遍历过程中，我们通过比较s[i]和s[j]的值，来更新指针j和next数组的值。具体的操作如下：
- 如果s[i]和s[j]相等，说明当前的字符可以加入到已知的最长相同前缀后缀中，所以我们将指针j加1，并将j的值存入next数组的当前位置。
- 否则，我们需要寻找更短的相同前缀后缀，所以我们将指针j回退到前一个位置，通过next[j-1]来获取更短的相同前缀后缀的长度。我们将比较s[i]和s[j-1]的值，直到找到一个相等的字符或者j回退到0为止。
- 如果j回退到0仍然没有找到相等的字符，说明当前位置不存在相同的前缀后缀，所以将指针i加1，并将j的值0存入next数组的当前位置。
- 如果找到了一个相等的字符s[i]和s[j-1]，说明我们找到了一个更短的相同前缀后缀，所以我们将指针j加1，并将j的值存入next数组的当前位置。
- 遍历结束后，我们可以得到一个完整的next数组，其中的每个值都代表了相应位置的最长相同前缀后缀的长度。
通过getNext方法计算得到的next数组，可以用于优化字符串匹配算法，如KMP算法等。在本段代码中，我们利用next数组的最后一个值，来判断字符串是否是由重复的子串组成的。
