字符串——459. 重复的子字符串

1 题目描述

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

2 题目示例

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

示例 2:
输入: s = “aba”
输出: false

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

3 题目提示

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

4 思路

方法一：字符串匹配
我们可以把字符串 ss 写成s’s’···s’s’的形式。

如果我们移除字符串s的前n’个字符（即一个完整的s’)，再将这些字符保持顺序添加到剩余字符串的末尾，那么得到的字符串仍然是s。由于1 ≤ n’≤ n，那么如果将两个s连在一起，并移除第一个和最后一个字符，那么得到的字符串—定包含s，即s是它的一个子串。
因此我们可以考虑这种方法:我们将两个s连在一起，并移除第一个和最后一个字符。如果s是该字符串的子串，那么s就满足题目要求。
证明需要使用一些同余运算的小技巧，可以见方法三之后的「正确性证明」部分。这里先假设我们已经完成了证明，这样就可以使用非常简短的代码完成本题。在下面的代码中，我们可以从位置 11 开始查询，并希望查询结果不为位置 nn，这与移除字符串的第一个和最后一个字符是等价的。

复杂度分析

由于我们使用了语言自带的字符串查找函数，因此这里不深入分析其时空复杂度。

方法二：：KMP 算法
由于本题就是在一个字符串中查询另一个字符串是否出现，可以直接套用 KMP 算法。因此这里对 KMP 算法本身不再赘述。读者可以自行查阅资料进行学习。

5 我的答案

class Solution {
    
    public boolean repeatedSubstringPattern(String s) {
    
        return (s + s).indexOf(s, 1) != s.length();
    }
}

class Solution {
    
    public boolean repeatedSubstringPattern(String s) {
    
        return kmp(s + s, s);
    }

    public boolean kmp(String query, String pattern) {
    
        int n = query.length();
        int m = pattern.length();
        int[] fail = new int[m];
        Arrays.fill(fail, -1);
        for (int i = 1; i < m; ++i) {
    
            int j = fail[i - 1];
            while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
    
                j = fail[j];
            }
            if (pattern.charAt(j + 1) == pattern.charAt(i)) {
    
                fail[i] = j + 1;
            }
        }
        int match = -1;
        for (int i = 1; i < n - 1; ++i) {
    
            while (match != -1 && pattern.charAt(match + 1) != query.charAt(i)) {
    
                match = fail[match];
            }
            if (pattern.charAt(match + 1) == query.charAt(i)) {
    
                ++match;
                if (match == m - 1) {
    
                    return true;
                }
            }
        }
        return false;
    }
}