KMP算法

KMP算法

簡介

一種由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.Pratt)三人設(shè)計的線性時間字符串匹配算法。該算法主要解決的就是字符串匹配的問題。
本文參考前綴函數(shù)與KMP算法-oi.wiki

例題

LeetCode 28：找出字符串種第一個匹配項的下標(biāo)
給你兩個字符串 haystack 和 needle ，請你在 haystack 字符串中找出 needle 字符串的第一個匹配項的下標(biāo)（下標(biāo)從 0 開始）。
如果 needle 不是 haystack 的一部分，則返回  -1 。

1 <= haystack.length, needle.length <= 104

haystack 和 needle 僅由小寫英文字符組成

輸入：haystack = "sadbutsad", needle = "sad"
輸出：0
解釋："sad" 在下標(biāo) 0 和 6 處匹配。
第一個匹配項的下標(biāo)是 0 ，所以返回 0 。

前置知識

• 字符串前綴
  假設(shè)有一個字符串 s[0...i] (下標(biāo)為0 - i)
  它的前綴就定義為 s[0...j] (j <= i)，當(dāng) j < i 時，就定義為該字符串的真前綴
• 字符串后綴
  同理
  后綴定義為 s[j...i] (j >= 0), 當(dāng) j > 0 時，就定義為該字符串的真后綴

前綴函數(shù) next[] 數(shù)組

next數(shù)組是KMP的核心

定義

給定一個長度為 n 的字符串 s，其 前綴函數(shù) 被定義為一個長度為 n 的數(shù)組 next。 其中 next[i] 的定義是：
如果子串 s[0...i] 有一對相等的真前綴與真后綴：s[ 0...k-1 ] 和 s[ i-(k-1)...i ] ( k-1 < i-(k-1) )，那么 next[i] 的值就是這個字符串最長的真前后綴（因?yàn)橄嗟鹊恼媲昂缶Y可能不止一對，所以需要的是最長的真前后綴）的長度，也就是 next[i] = k；
next[i] = max(k,max) //條件：([0...k-1] == s[i-(k-1)...i])
初始化 next[0] = 0

舉例

對于字符串: a b a b a b a c
next 數(shù)組：[ 0,0,1,2,1,2,3,0 ] => "","","a","ab","a","ab","aba",""

暴力求解 next 數(shù)組

給定字符串 s
暴力求解：
雙指針遍歷 s，設(shè)雙指針 i 為當(dāng)前 s[0...i] 的前綴和的下標(biāo)（截至下標(biāo)），j 為遍歷 0 - i 的下標(biāo)（遍歷匹配 s[j] 和 s[i-j]）
假設(shè)字符串 s[0...i] => j 遍歷 比較 s[0] == s[i] ... s[1] == s[i-1] ... s[j] == s[i-j] (需要滿足要求 j < i-j )
代碼如下（Java）：

public static int[] prefixFunction(String str){
    int[] next = new int[str.length()];
    // next[0] = 0; // 可以省略，默認(rèn)為 0
    for(int i = 1; i < str.length(); i++){
        for(int j = 0; j < i; j++){
            // 截取 str[0...j] 和 str[i-j...i] 比較 
            if(i-j > j && str.substring(0,j+1).equals(str.substring(i-j,i+1))){
                next[i] = j+1;
            }
        }
    }
    return next;
}
時間復(fù)雜度 O(n^3) 不推薦使用

優(yōu)化思想

• 優(yōu)化 1
  對于 next[i] ,當(dāng) s[i] == s[next[i-1]] 時 可以有 next[i] = next[i-1] + 1: （為什么呢??，別急看下面）
  假設(shè)字符串：a b c a b c 現(xiàn)在有 i = 5
  已求 next ：[0,0,0,1,2,?] next[5] = 2,現(xiàn)在 s[5] == s[2] , 有 next[5] == 3
  仔細(xì)想 對于 next[i] 來說，需要求的是 s[0...k] == s[i-k...i]
  而已經(jīng)有的 next[i-1] = m,所以已經(jīng)知道的信息是 s[0...m-1] == s[i-m...i-1] ,而現(xiàn)在又有 s[m] = s[i],那自然能推出 s[0...m] == s[i-m...i] ,所以 m + 1一定是 滿足next[i] 的一個前后綴相等的一個長度，那么我們?nèi)绾未_定是最大的呢
  假設(shè)他現(xiàn)在不是最大，存在一個更大的 next[i] == k + 1 ,那就有 s[0...k] == s[i-k...i] (k > m ),
  那么對于 next[i-1] 而言他也能找到 s[0...k-1] == s[i-k...i-1] (k > m) 那么 next[i-1] 就應(yīng)該是 k 了，而不是 m ，這顯然是矛盾的，所以 k 并不存在，m + 1 就是next[i] 的最大前后綴相等長度
  總結(jié) if( s[i] == s[next[i-1]] ) next[i] = next[i-1] + 1
• 優(yōu)化 2 (最難理解的部分來了，如果感覺看不懂可以考慮結(jié)合 oi.wiki 的一些圖解增強(qiáng)理解)
  對于 next[i] ,當(dāng) s[i] != s[next[i-1]] 時, 考慮 next[i-1]的第二長前綴和長度開始 ,假設(shè) 第二長度 為 j 那么同理的 我們可以比較 s[i] == s[j],再不行就第三長...
  例如 ： a b c a b d a b c a b c 此時 i == 11
  next[]:[0,0,0,1,2,0,1,2,3,4,5,?]

 a b c a b 是i-1最長 => s[0...4] == s[10 - 4...10]  
 a b 是第二長 => s[0...1] == s[10 - 1...10]
 現(xiàn)在的問題是如何求 第二長 j (這里 j == 2） i == 11，next[i-1] == 5)
 已知： next[i-1] = 5
 因?yàn)橛?s[0...4] == s[6...10] ,所以有 s[0...1] == s[6...7] (s[0...j-1] == s[i - next[i - 1]...i - next[i - 1] + j)
 而 又因?yàn)?s[0...1] == s[10 - 1...10] == s[4 - 1...4] (s[0...j-1] == s[i-j...i-1] == s[next[i-1] - j...next[i-1]-1])
 所以有 s[0...j-1] == s[next[i-1] - j ... next[i-1]-1] ，仔細(xì)觀察會發(fā)現(xiàn)這其實(shí)就是 下標(biāo)為 next[i-1] - 1 的最長前后綴相等長度
 所以有 j = next[next[i-1] - 1]
 同理 第三長就是 next[next[next[i-1]- 1] - 1]

優(yōu)化求解 next 數(shù)組

結(jié)合前面兩個優(yōu)化

public static int[] prefixFunctionAdvance(String str){
    int[] next = new int[str.length()];
    for(int i = 1; i < next.length; i++){
        int j = next[i-1];
        while(j > 0 && str.charAt(i) != str.charAt(j))  j = next[j-1];
        if(j < i-j && str.charAt(i) == str.charAt(j)) j++;
        next[i] = j;
    }
    return next;
}

解例題

現(xiàn)在我們知道了怎么求 next 數(shù)組，想要解這個例題其實(shí)很簡單
嘗試將兩個字符串合并，使用 '#' 字符區(qū)別開（'#' 可以替換，只需要滿足兩個字符串中都不會出現(xiàn)該字符）：
合并前： haystack = "sadbutsad", needle = "sad"
合并后： s = "sad#sadbutsad"
然后對 s 求 next 數(shù)組
next數(shù)組中第一次出現(xiàn) next[i] == needle.lenght() 時，那么這就是 needle 第一次出現(xiàn)的位置
【注】：因?yàn)榍熬Y式中有個字符'#'是不可能出現(xiàn)相等的，所以不可能存在前后綴最大和 > needle.length()

public int solution(String haystack,String needle){
    String s = needle + "#" + haystack;
    int[] ints = prefixFunctionAdvance(s);
    for(int i = 0; i < ints.length; i++){
        if(ints[i] == needle.length()){
            // i - needle.len + 1為 next中出現(xiàn)重復(fù)的開始下標(biāo)，需要減去 needle + "#" 的長度才是 haystack 的下標(biāo)
            // return i - needle.length() + 1 - (needle.length() + 1); 
            // 化簡后
            return i - needle.length() * 2;
        }
    }
    return -1;
}