Java中字符串匹配KMP算法怎么寫

這篇文章主要講解了“Java中字符串匹配KMP算法怎么寫”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Java中字符串匹配KMP算法怎么寫”吧！

暴力的字符串匹配算法很容易寫，看一下它的運行邏輯：

public class bf {    public static int search(String txt,String pat){        int sLen = txt.length();// 主字符串        int pLen = pat.length();// 模式串長度        // 需要匹配的次數        for (int i=0;i<=sLen-pLen;i++){            int j ;            // 遍歷模式串            for (j=0;j<pLen;j++){                if (pat.charAt(j)!=txt.charAt(i+j)){                    break;                }            }            // 如果j移動到模板末尾了 說明匹配成功了            if (j==pLen) return i ;        }        return -1;    }    public static void main(String[] args) {        System.out.println(search("aaacaaab","ababac"));    }}

對于暴力算法，如果出現不匹配字符，同時回退 txt 和 pat 的指針，嵌套 for 循環，時間復雜度 $O(MN)$，空間復雜度$O(1)$。最主要的問題是，如果字符串中重復的字符比較多，該算法就顯得很蠢。

比如 txt = "aaacaaab" pat = "aaab"：

求

KMP分為兩部分，next 數組 和 正式匹配

next 數組 部分：開一個數組next，找每個字符前的 最大相等前后綴長度，我簡單地通過舉例解釋一下這個詞：

比如 aba --> 一個前綴是 a，一個后綴是 a，最大相等前后綴長度 為 1

比如 baba --> 一個前綴是 ba，一個后綴是 ba，最大相等前后綴長度 為 2

比如 ababa --> 一個前綴是 aba，一個后綴是 aba，最大相等前后綴長度 為 3，為什么不是前綴 ababa，后綴 ababa 呢，是因為前綴不包含最后一個字符，后綴不包含第一個字符。為什么不是前綴 a 后綴 a 呢，因為盡管它們是一對相等前后綴，但它們不是 最大 相等前后綴長度

設置i j指針，i j最初位于開頭和索引為 1 的位置，分別代表前綴，后綴指針，前綴后綴串有個特點：前綴串總是從0開始，而后綴串總是相對于前綴串(不能確定開始的位置)，因此每當 i j 失配時，i 就回溯到上一個位置，那 i 怎么回到上一個位置，這個地方是最難理解的：next[i] 就是 i 應該回到的位置（ps:如果你是為了考試但還不能理解，建議背下來，可以不用花時間去理解了，始終記住一回溯就是 i = next[i]，如果放一堆證明公式在這里，相信肯定令人昏昏欲睡！）然后進行下一輪匹配，直到 j 走完了，next數組才算完成

正式匹配 部分：現在來討論主串與模式串的關系了，主串就是被匹配的串，模式串是要拿去匹配的其他字符串的字符串(有點拗口)，通常模式串長度小于主串。用 i j 作為主串 模式串的指針，這時模式串是相對的，主串是絕對的，因為主串匹配不上就得往后走，而模式串匹配不上就得再重新匹配前面一部分，因此每當 i j 失配時，j 就回溯到上一個位置(這里的回溯同理)，進行下一輪匹配，直到 j 走完了，說明匹配成功，返回 i - j，因為i - j 對應的就是匹配到的起始位置。若匹配不上的話，i 就走到結尾了，返回 -1

感謝各位的閱讀，以上就是“Java中字符串匹配KMP算法怎么寫”的內容了，經過本文的學習后，相信大家對Java中字符串匹配KMP算法怎么寫這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！