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

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

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

public class bf {    public static int search(String txt,String pat){        int sLen = txt.length();// 主字符串        int pLen = pat.length();// 模式串長(zhǎng)度        // 需要匹配的次數(shù)        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移動(dòng)到模板末尾了 說明匹配成功了            if (j==pLen) return i ;        }        return -1;    }    public static void main(String[] args) {        System.out.println(search("aaacaaab","ababac"));    }}

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

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

求

KMP分為兩部分，next 數(shù)組 和 正式匹配

next 數(shù)組 部分：開一個(gè)數(shù)組next，找每個(gè)字符前的 最大相等前后綴長(zhǎng)度，我簡(jiǎn)單地通過舉例解釋一下這個(gè)詞：

比如 aba --> 一個(gè)前綴是 a，一個(gè)后綴是 a，最大相等前后綴長(zhǎng)度 為 1

比如 baba --> 一個(gè)前綴是 ba，一個(gè)后綴是 ba，最大相等前后綴長(zhǎng)度 為 2

比如 ababa --> 一個(gè)前綴是 aba，一個(gè)后綴是 aba，最大相等前后綴長(zhǎng)度 為 3，為什么不是前綴 ababa，后綴 ababa 呢，是因?yàn)榍熬Y不包含最后一個(gè)字符，后綴不包含第一個(gè)字符。為什么不是前綴 a 后綴 a 呢，因?yàn)楸M管它們是一對(duì)相等前后綴，但它們不是 最大 相等前后綴長(zhǎng)度

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

正式匹配 部分：現(xiàn)在來討論主串與模式串的關(guān)系了，主串就是被匹配的串，模式串是要拿去匹配的其他字符串的字符串(有點(diǎn)拗口)，通常模式串長(zhǎng)度小于主串。用 i j 作為主串 模式串的指針，這時(shí)模式串是相對(duì)的，主串是絕對(duì)的，因?yàn)橹鞔ヅ洳簧暇偷猛笞撸Ｊ酱ヅ洳簧暇偷迷僦匦缕ヅ淝懊嬉徊糠?，因此每?dāng) i j 失配時(shí)，j 就回溯到上一個(gè)位置(這里的回溯同理)，進(jìn)行下一輪匹配，直到 j 走完了，說明匹配成功，返回 i - j，因?yàn)閕 - j 對(duì)應(yīng)的就是匹配到的起始位置。若匹配不上的話，i 就走到結(jié)尾了，返回 -1

感謝各位的閱讀，以上就是“Java中字符串匹配KMP算法怎么寫”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)Java中字符串匹配KMP算法怎么寫這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！