字符串——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 数据处理
|
6月前
|
并行计算
求无重复字符的最长子串
求无重复字符的最长子串
|
6月前
|
索引 容器
06-数据容器str(字符串)-字符串的下标索引/字符串无法修改/查找字符串下标初始值/字符串的替换/字符串的分割/字符串去除前后空格/统计字符串的数量/字符串的循环遍历/对字符串进行分割
06-数据容器str(字符串)-字符串的下标索引/字符串无法修改/查找字符串下标初始值/字符串的替换/字符串的分割/字符串去除前后空格/统计字符串的数量/字符串的循环遍历/对字符串进行分割
|
6月前
|
人工智能 算法 测试技术
【字符串】【C++算法】828.统计子串中的唯一字符
【字符串】【C++算法】828.统计子串中的唯一字符
|
11月前
|
C++
C/C++判断字符串是否为另一字符串的子字符串
C/C++判断字符串是否为另一字符串的子字符串
135 0
7-121 删除字符串中的子串
7-121 删除字符串中的子串
67 0
C 去除字符串中重复字母(LeetCode)
摆烂太久,好久没有更文了,小九和大家一起看看题写写题找回手感吧,也希望这篇文章可以帮助正在寻找解题答案的朋友,你们的支持就是我最大的动力!求三连!求关注呀!🌟。
C  去除字符串中重复字母(LeetCode)
|
Java
给定一个字符串和一个子串。子串中的字符可能重复,输出子串出现的次数。(Java实现)
给定一个字符串和一个子串。子串中的字符可能重复,输出子串出现的次数。(Java实现)
117 0
给定一个字符串和一个子串。子串中的字符可能重复,输出子串出现的次数。(Java实现)