# 题目

459. 重复的子字符串 - 力扣（LeetCode）

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过 10000。

示例 1:

• 输入: "abab"
• 输出: True
• 解释：可由子字符串 "ab" 重复两次构成。

示例 2:

• 输入: "aba"
• 输出: False

示例 3:

• 输入: "abcabcabcabc"
• 输出: True
• 解释：可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

#

# 分析

# 移动匹配

如果为 ture，则说明字符串里必定有最小组成单元

那么如果把两个字符串组合成新的字符串，然后掐头去尾，如果新字符串里包含原字符串，则说明里面有最小组成串

// 时间复杂度: O (n)

// 空间复杂度: O (1)

class Solution {

public:

    bool repeatedSubstringPattern(string s) {

        string t = s + s;

        t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾

        if (t.find(s) != std::string::npos) return true; //std::string::npos 是 find 方法的返回值，说明没有找到

        return false;

    }

};

# kmp

代码随想录 (programmercarl.com)