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

短命女 2023-10-08 16:09 36阅读 0赞

## 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;
        }
    }