459. 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

class Solution {
public:
    void getnext(string& s,int *next)
    {
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.size(); i++)
        {
            while (j >= 0 && s[i] != s[j + 1])
            {
                j = next[j];
            }
            if (s[i] == s[j + 1]) j++;

            next[i] = j;
        }
    }
    bool repeatedSubstringPattern(string s) {
        string::size_type len = s.size();
        if (len == 0) return false;
        int *next = new int[len];
        getnext(s, next);
        //找最小重复子串的长度 = 整个s的最长前缀的末尾到s末尾组成的字符串的长度
        int res = next[len - 1];
        if (res == -1) return false;
        //最小重复子串的长度
        int len1 = len - res - 1;
        //长度可以被len整除 说明该字符串有重复的子字符串。
        if (len % len1 == 0) return true;
        else {
            return false;
        }
    }
    bool repeatedSubstringPattern1(string s)
    {
        //将两个字符拼在一起，去掉头部和尾部的一个字符，如果能找到原字符串 则说明由重复字符构成
        string ss = s + s;
        ss.erase(ss.begin());
        ss.erase(ss.end() - 1);
        const auto res = ss.find(s);
        if (res != string::npos)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};