0459. Repeated Substring Pattern ================================ 题目信息 -------- :题号: 0459 :难度: Easy :主题: 小写字符串、非空子串、完整重复、模式判断 :原题: `LeetCode 0459 `_ :重点: 基本子串必须比原串短、从头到尾连续重复至少两次、不能遗漏或重排字符 题目重述 -------- 给定只包含小写英文字母的非空字符串 ``s``,判断是否存在一个非空且长度小于 ``s`` 的字符串 ``t``,使 ``s`` 恰好由 ``t`` 连续重复若干次组成。 重复次数必须至少为 2,所有字符都必须被完整覆盖,不能只让某个前缀或子串满足重复关系。``s.length`` 位于 ``[1, 10^4]``。 自建示例 -------- 同一模式重复三次: .. code-block:: text 输入:s = "abcabcabc" 输出:true 解释:字符串可由非空子串 abc 连续重复 3 次得到。 前后局部相似但不能完整重复: .. code-block:: text 输入:s = "abac" 输出:false 解释:不存在一个较短子串能够从头到尾重复并恰好覆盖全部四个字符。 利用重复串的旋转性质 -------------------- 若 ``s`` 由某个更短模式重复组成,那么把 ``s`` 与自身拼接后,除去最左和最右的一个完整边界,仍会在中间找到一次完整的 ``s``。反过来,若 ``s`` 在 ``(s+s)`` 的位置 1 之后再次出现,这个出现位置提供的周期会把原串分解为至少两段相同模式。 长度为 1 的字符串必须排除,因为它的双倍串从位置 1 也能找到自身,但不存在更短的非空模式。 C++ 实现 -------- .. code-block:: cpp 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)``。