跳转至

459. 重复的子字符串

力扣链接(简单)：https://leetcode.cn/problems/repeated-substring-pattern

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

  • 1 <= s.length <= 104
  • s 由小写英文字母组成

个人题解

时间复杂度：\(O(n)\)

C++
 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
28
29
class Solution {
public:
    // KMP 算法具体见 28. 找出字符串中第一个匹配项的下标
    void getNext(int* next, string& s) {
        // 初始化 next
        int j = 0;
        next[0] = j;
        for(int i = 1; i < s.size(); i++){
            // 匹配失败情况，回退
            while(j > 0 && s[i] != s[j]) j = next[j - 1]; 
            // 匹配成功，继续向后
            if(s[i] == s[j]) j++;
            // 更新 next
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern(string s) {
        int next[s.size()];
        getNext(next, s);

        int len = s.size();
        // 首先最长相等前后缀不能为0，这代表没有任何重复子串了
        // 其次，字符串长度正好可以被(串长度-最长相等前后缀)整除，说明是有周期性的
        // 最好用几个测试用例把 next 数组打印一下就明白为什么这样可以确定周期性
        if(next[len - 1] != 0 && len % (len - next[len - 1]) == 0)
            return true;
        return false;
    }
};