字符串——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;
    }
}
相关文章
|
6月前
|
存储
【字符串】最长不含重复字符的子字符串
【字符串】最长不含重复字符的子字符串
|
3月前
|
Java
输入一个字符串,找出其中不含有重复字符的最长子串的长度。
这篇文章提供了一个Java解决方案,用于找出输入字符串中不含有重复字符的最长子串的长度,通过使用HashSet来跟踪字符并计算最长不重复字符子串。
输入一个字符串,找出其中不含有重复字符的最长子串的长度。
|
5月前
3. 无重复字符的最长子串
3. 无重复字符的最长子串
|
6月前
|
并行计算
求无重复字符的最长子串
求无重复字符的最长子串
|
11月前
|
C++
C/C++判断字符串是否为另一字符串的子字符串
C/C++判断字符串是否为另一字符串的子字符串
127 0
|
11月前
|
C++
C++中从一个字符串中截取另一长度的子字符串
C++中从一个字符串中截取另一长度的子字符串
60 0
无重复字符的最长子串
写一个if语句,当left小于right的时候,就写一个循环遍历从left下标开始的元素到right下标前面的元素,判断是否与right下标的元素相同,相同的话就跳出循环,令left 等于 与 right下标元素相同的元素后面的元素.怎么判断在left和right之间是否存在又和right相同的元素呢?这就用到了falg.如果left < right 的时候就让 right++; max = max = right - left + 1。
54 0
7-121 删除字符串中的子串
7-121 删除字符串中的子串
67 0
|
Java
给定一个字符串和一个子串。子串中的字符可能重复,输出子串出现的次数。(Java实现)
给定一个字符串和一个子串。子串中的字符可能重复,输出子串出现的次数。(Java实现)
116 0
给定一个字符串和一个子串。子串中的字符可能重复,输出子串出现的次数。(Java实现)