#字符串 #重复的子字符串

repeated-substring-pattern.cpp

class Solution {
public:

    void get_pmt(const string& s, int*pmt) {
        pmt[0] = 0;
        int j = 0;
        for (int i = 1; i < s.size(); ++i) {
            while (j > 0 && s[i] != s[j])
                j = pmt[j - 1];
            if (s[i] == s[j])
                j++;
            pmt[i] = j; 
        }
    }

    bool repeatedSubstringPattern(string s) {
        if (s.size() <= 1)
            return false;
        int pmt[s.size()];
        get_pmt(s, pmt);
        
        // aabc aabc aabc
        // 0100 1234 5678

        // abc abcabcabc"
        // 000 123456789

        // aaaaaaaa
        // 01234567

        // abab
        // 0012

        // abac
        // 0010

        int k = s.size() - pmt[s.size() - 1];
        if (pmt[s.size() - 1] > 0 && s.size() % k == 0)
            return true;
        else 
            return false;
    }
};