题目

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

跟着代码随想录的思路走了一遍，使用kmp算法去解决这道题，同时巩固了kmp算法

首先就是创建next表，这个是kmp算法的关键，我就习惯用-1的表了，需要注意的是，在遍历模式串的时候，要先写while退回的，再写if前进的，不然到时候退回了，如果后面还有相等就没法加上，next就出错了。

进入主代码，卡哥用大量的篇幅去证明一个事情，最大相等前后缀不包含的字串，如果是存在，并且是可以整除模式串的，那么这个模式串就是重复的子字符串。总结出来就是一句代码的事情，但是证明起来却需要理解良久。

class Solution {
public:
    void getNext(vector<int>& next, const string& s) {
        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) {
        if (s.size() == 0) {
            return false;
        }
        vector<int> next(s.size());
        getNext(next,s);
        int len = s.size();
        if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) {
            return true;
        }
        return false;
    }
};