Repeated Substring Pattern.cpp

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int len = s.size();
        if(!len)return true;
        vector<int> next(len + 1, -1);
        int i = 0, k = -1;
        while(i < len)
        {
            if(k == -1 || s[i] == s[k])
                next[++i] = ++k;
            else
                k = next[k];
        }
        return next[len] > 0 && len % (len - next[len]) == 0;
    }
};