题目

点击前往

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1：

1
2
3
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2：

1
2
输入: s = "aba"
输出: false

示例 3：

1
2
3
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

解题思路

  • 使用KMP算法。
  • next 数组记录的是最长相同前后缀，如果 next[len - 1] != -1，则说明字符串有最长相同的前后缀。
  • 最长相等前后缀的长度为：next[len - 1]。
  • 数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function(s) {
    if (s.length === 0)
        return false;
    const getNext = (s)=>{
        let next = new Array();
        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;
};