[leetcode] [KMP] KMP

ABCDABD...

ABCDABF...

簡單的說, 傳統解兩字串匹配部分

可能會來個雙迴圈, 哀個比對, 當不匹配的時候, 會將下方列再後移1位

然後不匹配再後移

然而

如果像上放已經有4個屬於匹配的字串, 她就應該直接往後移四位來匹配, 而不是只移動1位

隱藏的思維是, 當已知匹配的, 就已知完全不能匹配的部分, 而這部分應該合理的跳過

而當它既是前墜又是後墜的時候, 可能前面就都相同可以跳過

直接開始比開始不同的地方

後贅數組定義, 是整個kmp算法根基

dp[i]: the max length k s.t. s[0:k-1] = s[i-k+1:i]

[x x x] x [x x i]

中心思想, 是得到一個next數組 類似[-1, -1, 0, 1]

當該數位置對應的數字找不到匹配時, 可往前跳向下標位置再進行比對

(網路上有不同解法有跳往下標, 或是前一個下標, 會反應在j的初始值-1或是0)

public static boolean repeatedSubstringPattern(String s) {

    if(s.equals(""))return false;

    int len = s.length();
    int[] temp = new int[len];
    int[] next=getNext(temp,s, len);
    // 比對表最後一欄位置不為-1 且 長度能被最大重複組除盡
    if (next[len-1] != -1 && len % (len - (next[len-1]+1)) == 0) {
        return true;
    }

    return false;
}

public static int[] getNext(int[]next, String s, int len){
    // 1 初始化賦予-1值
    next[0] = -1;
    int j = -1;
    char[] chars = s.toCharArray();

    for(int i = 1; i<len; i++){
        // 2 前後綴不相等時, 往前跳到指定位置再進行下迴圈(比對)
        while(j>=0&&chars[i]!=chars[j+1]){
            j = next[j];
        }
        // 3 前後綴相等, j++, 並將值放到next表中
        if(chars[i]==chars[j+1]){
            j++;
        }
        next[i]=j;
    }
    return next;
}

參考: https://www.youtube.com/watch?v=t6xa2p6fFS8&t=918s