KMP算法

算法的背景

KMP 是一個解決模式串在文本串是否出現(xiàn)過，如果出現(xiàn)過，最早出現(xiàn)的位置的經(jīng)典算法

核心思想

KMP 方法算法就利用之前判斷過信息，通過一個 next 數(shù)組，保存模式串中前后最長公共子序列的長度，每次回溯時(shí)，通過 next 數(shù)組找到，前面匹配過的位置，省去了大量的計(jì)算時(shí)間。

算法圖解：

當(dāng)算法移動到上述位置時(shí)：（發(fā)生不匹配）

發(fā)現(xiàn)公共前后綴為A，于是移動公共前后綴到下面位置：

為什么能夠保證移動時(shí)就不會出現(xiàn)再匹配的情況呢

因?yàn)檫@里可以采用反證的手段，如果在移動時(shí)出現(xiàn)匹配，則就說明公共前后綴與所確定的模式串的公共前后綴不同，這就產(chǎn)生矛盾了。

KMP算法的思考

核心代碼

求next數(shù)組（這里next數(shù)組表示模式串的公共前后綴個數(shù)）

//獲取字符串的部分匹配值表 ? ?public static int[] kmpNext(String dest){ ? ? ? ?int[] next = new int[dest.length()]; ? ? ? ?next[0] = 0; ? ? ? ?for (int i = 1, j = 0; i < dest.length(); i++) {//j可以代表匹配時(shí)的一個計(jì)算變量 ? ? ? ? ? ?if(dest.charAt(i) == dest.charAt(j)) { ? ? ? ? ? ? ? ?j++; ? ? ? ? ? ?}else{ ? ? ? ? ? ? ? ?j = next[j - 1];//如果出現(xiàn)匹配不成功則直接賦值0 ? ? ? ? ? ?} ? ? ? ? ? ? ? ?next[i] = j;//找到i對應(yīng)的j值，比如第一個字母A就是1，AB就是2 ? ? ? ?} ? ? ? ?return next; ? ?}

求KMP算法：

public static int kmpSearch(String str1,String str2,int[] next){ ? ? ? ?for (int i = 0,j = 0; i < str1.length(); i++) {//這里使用兩個指針進(jìn)行匹配 ? ? ? ? ? ?while(j > 0 && str1.charAt(i) != str2.charAt(j)){ ? ? ? ? ? ? ? ?j = next[j - 1];//這里是核心中的核心 ? ? ? ? ? ?} ? ? ? ? ? ?if(str1.charAt(i) == str2.charAt(j)){ ? ? ? ? ? ? ? ?j++;//指針前移 ? ? ? ? ? ?} ? ? ? ? ? ?if(j == str2.length()){ ? ? ? ? ? ? ? ?return i - j + 1;//這加個1是因?yàn)榭紤]到索引問題 ? ? ? ? ? ?} ? ? ? ?} ? ? ? ?return -1; ? ?}

鏈接：https://www.dianjilingqu.com/617758.html