0459. Repeated Substring Pattern

题目信息

题号:

0459

难度:

Easy

主题:

小写字符串、非空子串、完整重复、模式判断

原题:

LeetCode 0459

重点:

基本子串必须比原串短、从头到尾连续重复至少两次、不能遗漏或重排字符

题目重述

给定只包含小写英文字母的非空字符串 s,判断是否存在一个非空且长度小于 s 的字符串 t,使 s 恰好由 t 连续重复若干次组成。

重复次数必须至少为 2,所有字符都必须被完整覆盖,不能只让某个前缀或子串满足重复关系。s.length 位于 [1, 10^4]。

自建示例

同一模式重复三次:

输入:s = "abcabcabc"
输出:true
解释:字符串可由非空子串 abc 连续重复 3 次得到。

前后局部相似但不能完整重复:

输入:s = "abac"
输出:false
解释:不存在一个较短子串能够从头到尾重复并恰好覆盖全部四个字符。

利用重复串的旋转性质

若 s 由某个更短模式重复组成,那么把 s 与自身拼接后,除去最左和最右的一个完整边界,仍会在中间找到一次完整的 s。反过来,若 s 在 (s+s) 的位置 1 之后再次出现,这个出现位置提供的周期会把原串分解为至少两段相同模式。

长度为 1 的字符串必须排除,因为它的双倍串从位置 1 也能找到自身,但不存在更短的非空模式。

C++ 实现

class Solution {
public:
    bool repeatedSubstringPattern(std::string s) {
        if (s.size() <= 1) return false;
        std::string doubled = s + s;
        return doubled.find(s, 1) != s.size();
    }
};

代码分析

从位置 1 开始查找并排除末尾位置 s.size() 的原始副本,只有中间再次出现才说明存在严格更短的周期。该实现依赖标准字符串查找,空间复杂度为 O(n);若按库实现的查找复杂度计,时间不超过常见的 O(n^2),也可由线性匹配算法优化到 O(n)。