Problem: ************

思路

这题的思路除去枚举方法外，可以使用一个巧妙的方法，将字符串加倍，然后将头部和尾部的一个字符删除，再判断是否能从中找到响应的字符串。

解题方法

例如字符串“abab”,将其加倍变成“abababab”，删掉头部和尾部的一个字符，变成“bababa”，在从中判断是否有“abab”字符串。

复杂度

• 时间复杂度:

由于使用的是库函数find进行查找，因此时间复杂度不用讨论

• 空间复杂度:

由于在本身结构上完成，空间复杂度为$O(1)O(1)$

Code

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

拓展

可以将题目进一步拓展为：

定义重复字符串是由两个相同的字符串首尾拼接而成。例如："abcabc" 是一个长度为 6 的重复字符串，因为它由两个 "abc" 串拼接而成；"abcba" 不是重复字符串，因为它不能由两个相同的字符串拼接而成。给定一个字符串，请返回其最长重复子串的长度。若不存在任何重复字符子串，则返回 0。

class Solution {
public:
    int solve(string a) {
        int n=a.size();
        int ans=0;
        for(int i=n/2;i>0;--i)//长度大于字符串长度一半的子串，必然不存在同样的拷贝在其后面。
        {
            for(int j=0;j<n-i;++j)//拷贝起点
            {
                if(a[j]==a[i+j])
                {
                    ++ans;
                }
                else
                {
                    ans=0;//不满足条件，重置长度
                }
                if(ans==i) return ans*2;//一旦=i,那就是最大的长度
            }
        }
        return 0;
    }
};

复杂度

• 时间复杂度:

$O(n^2)O(n^2)$

• 空间复杂度:

由于在本身结构上完成，空间复杂度为$O(1)O(1)$