459. 重複的子字元串(KMP算法)

​​459. 重複的子字元串​​

優秀解法：KMP(n,n)

• fail數組定義：最長前字尾長度-1 如ababab為3 最長前字尾為4：abab(第一個) abab(第二個)
• 初始值為什麼為-1：讓第一個if的now + 1 = 0 否則會少判斷第一個字母
• 怎麼加速獲得fail值：

• 如果s[now + 1] == s[i] 即在最長字首的後一個字母也和目前串下一個字母相同 那麼當然最長前字尾長度加一

• 如果不相等 那麼仍可利用原來的最長前字尾

  我們當然不想把這個長度縮小太多 因為我們要找的是最長相同字首字尾 那麼這個字首必定會在子串A 字尾必定會在子串B(因為這兩個子串完全相同)

  同時 因為子串A的字尾與子串B的字尾相同 那麼新最長相同前字尾長度等于子串A的最長相同前字尾長度 即 now = fail[now - 1](fail數組定義為最長相同前字尾長度的情況，下面的代碼定義為長度-1是以有所不同)，當終于P[now] = P[x]則可以向右擴充 或者始終不相等則從零開始

class Solution {
public:
    bool kmp(const string& s){
        int n = s.size();
        //将fail定義為最長相同前字尾長度 - 1  
        vector<int> fail(n,-1);
        for(int i = 1; i < n; i++){
            int now = fail[i - 1];
            //如果初始值是-1 那麼這裡是now + 1 如果是0 這裡是now 下面的指派同理
            while(now != -1 && s[now + 1] != s[i]){
                //如果始終不同 那麼始終縮短為a串的最長相同子字首直到now為-1或者相同了
                now = fail[now];
            }
            //前一個fail值的下一位和目前位相同的話 目前fail為前fail+1
            if(s[now + 1] == s[i]) fail[i] = now + 1;
        } 
        //第一個條件：隻有當原串有相同前字尾才有可能符合題意
        //第二個條件：規律：最長規律字串長度 = n - 最長前字尾 成倍數 
        return fail[n - 1] != -1 && n % (n - fail[n - 1] - 1) == 0;        
    }

    bool repeatedSubstringPattern(string s) {
        return kmp(s);
    }

    
};