​LeetCode刷题实战459：重复的子字符串

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 重复的子字符串，我们先来看题面：

https://leetcode-cn.com/problems/repeated-substring-pattern/

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

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

示例

示例 1:

输入: "abab"

输出: True

解释: 可由子字符串 "ab" 重复两次构成。

示例 2:

输入: "aba"

输出: False

示例 3:

输入: "abcabcabcabc"

输出: True

解释: 可由子字符串 "abc" 重复四次构成。(或者子字符串 "abcabc" 重复两次构成。)

解题

思路大致如下：如果一个非空字符串s可以由它的一个子串重复多次构成，可以理解为s中存在m个子串，那么当两个字符串结合起来变成ss时，字符串s在新字符串ss的第二次位置不等于s的长度（相当于前一个字符串s中有n个子串，在后一个字符串中有m-n个子串，所以此时的位置不等于s的长度）；反之，一个非空字符串s不可以由它的一个子串重复多次构成，那么当两个字符串结合起来变成ss时，字符串s在新字符串ss的第二次位置就在后一个字符串首字符的位置，其位置刚好等于s的长度。根据这一特征来判断。

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

上期推文：

LeetCode1-440题汇总，希望对你有点帮助！

LeetCode刷题实战441：排列硬币

LeetCode刷题实战442：数组中重复的数据

LeetCode刷题实战443：压缩字符串

LeetCode刷题实战444：序列重建

LeetCode刷题实战445：两数相加 II

LeetCode刷题实战446：等差数列划分 II - 子序列

LeetCode刷题实战447：回旋镖的数量

LeetCode刷题实战448：找到所有数组中消失的数字

LeetCode刷题实战449：序列化和反序列化二叉搜索树

LeetCode刷题实战450：删除二叉搜索树中的节点

LeetCode刷题实战451：根据字符出现频率排序

LeetCode刷题实战452：用最少数量的箭引爆气球

LeetCode刷题实战453：最小操作次数使数组元素相等

LeetCode刷题实战454：四数相加 II

LeetCode刷题实战455：分发饼干

LeetCode刷题实战456：132 模式

LeetCode刷题实战457：环形数组是否存在循环

LeetCode刷题实战458：可怜的小猪