現(xiàn)在寫文章吧凉，也是痛點(diǎn)在哪，就寫哪踏志？今天的痛點(diǎn)是老是記不住KMP算法阀捅。
我曾經(jīng)3次拿下KMP算法。但令人遺憾的是狰贯，我又忘記了也搓。
所以決定還是寫寫，這樣下次可以快速撿起來(lái)涵紊。網(wǎng)上有很多很好的KMP的學(xué)習(xí)材料傍妒。
一般都是從頭講起的。我這里推薦出來(lái)摸柄，給完全沒接觸過(guò)的KMP的小伙伴颤练。
KMP超詳細(xì)講解
上面這篇文章應(yīng)該是我看到的最好的講解了。

我下面的講解驱负，是從另一個(gè)角度去思考KMP算法的嗦玖。

KMP本身理解就比較復(fù)雜。如果我的講解跃脊，你們看不懂宇挫，可以去看我上面分享的。

1. 直覺

在計(jì)算機(jī)的世界里數(shù)據(jù)都是以01形式表示酪术。
比如有一串?dāng)?shù)據(jù)流是01110111101.
我們想在這串?dāng)?shù)據(jù)流中找到是否含有01111這個(gè)子串
那么在暴力做法時(shí)器瘪，我們匹配到第5個(gè)字符翠储，發(fā)現(xiàn)失配了。
那么人的直覺就是因?yàn)橐ヅ涞拇_頭是0. 一直匹配到第5個(gè)字符才不對(duì)橡疼，前面都對(duì)援所。那么必然為01110 所以我們可以直接把開頭的0移動(dòng)到失配的那個(gè)0上。
這樣就可以提高匹配速度欣除。

2. next array

lc 里有很多題目住拭，都可以通過(guò)初始化一個(gè)NEXT ARRAY來(lái)提高算法的時(shí)間復(fù)雜度。
TODO: 之后會(huì)補(bǔ)充例子進(jìn)來(lái)
NEXT ARRAY一般會(huì)去存历帚，從這個(gè)位置開始包括這個(gè)位置下一個(gè)J字符的INDEX是什么滔岳，如果之后沒有J字符了，那么就返回-1.
因?yàn)橐话泐}目會(huì)說(shuō)只有小寫字母抹缕。所以我們可以用26 * N的時(shí)間澈蟆，構(gòu)造好這個(gè)NEXT ARRAY。之后就可以實(shí)現(xiàn)O(1)的跳躍卓研。

// next array 構(gòu)造法
char[] cs = str.toCharArray();
int l = cs.length;
int[][] next = new int[l + 1][26];
Arrays.fill(next[l], -1);
for (int i = l - 1; i >= 0; i--) {
    next[i] = next[i+1].clone();
    next[i][cs[i]-'a'] = i;
}

為什么可以這么構(gòu)造趴俘？

核心就是從后往前，當(dāng)前這個(gè)字符只會(huì)改變這層狀態(tài)機(jī)的這個(gè)字符的狀態(tài)點(diǎn)奏赘。其余的字符都是繼承來(lái)自后面的狀態(tài)機(jī)的轉(zhuǎn)移寥闪。
如果后面有該字符（非本層字符），后一層的狀態(tài)機(jī)已經(jīng)掌握了最近的這個(gè)字符的下標(biāo)的INDEX磨淌。所以我這層就可以直接用疲憋。
如果是本層字符，顯然我自己最近梁只。我就用我自己就好了缚柳。

那么如何使用NEXT ARRAY呢？

比如我們要找一個(gè)串是不是目標(biāo)串的子序列搪锣。我們已經(jīng)把目標(biāo)串的NEXT ARRAY構(gòu)建出來(lái)后秋忙。可以用如下代碼快速判斷构舟。

int i = 0;
for (char c : cs) {
   i = next[i][c-'a'];
   if (i == -1) return false;
}
return true;

3. 有限確定狀態(tài)機(jī)

其實(shí)上面的NEXT ARRAY 就是一種有限確定狀態(tài)機(jī)灰追。他定義了你在哪個(gè)INDEX i下狀態(tài) 為J.應(yīng)該轉(zhuǎn)移去哪個(gè)INDEX。
任何狀態(tài)i, j 都對(duì)應(yīng)1個(gè)確定性的去處狗超。（只需查1次弹澎，就知道）
這個(gè)就是DFA， Deterministic finite state, 有限確定狀態(tài)機(jī)的思想努咐。
我們?nèi)绻堰@個(gè)思想引入到字符串匹配中苦蒿，就是思考如何構(gòu)造一個(gè)DFA，使得每一個(gè)狀態(tài)都有對(duì)應(yīng)的去處渗稍。
假設(shè)我們有了這個(gè)DFA數(shù)組刽肠，我們?nèi)绾卫盟焖倨ヅ渥址?/p>

for (int i = 0, j = 0; j < dfa.length && i < cs.length; i++) {
    j = dfa[j][cs[i]-'a'];
}
if (j == dfa.length) return i - j; // dfa走到終態(tài)了
return -1;

那么我們就把找匹配字符串的時(shí)間復(fù)雜度從暴力的O (N ^ 2) 優(yōu)化到了O (N)

下面就是如何去構(gòu)造這個(gè)DFA溃肪。
其實(shí)思想也是和NEXT ARRAY 非常相似免胃。也是分為2步音五。
大多數(shù)狀態(tài)是繼承上一層的，我這層只管正確的那個(gè)狀態(tài)進(jìn)行更新羔沙。
要更新的狀態(tài)躺涝，其實(shí)就是模式串和查找串字符相等的時(shí)候，我們需要推進(jìn)一格扼雏。

image.png

image.png

上圖應(yīng)該不難理解坚嗜。
下面就是其他不匹配的狀態(tài)是如何繼承的呢？
我們可以知道當(dāng)我們?cè)诘谝粋€(gè)字符時(shí)诗充，凡是不匹配的也只能回退到當(dāng)前苍蔬。因?yàn)橐呀?jīng)退無(wú)可退。隨后的不匹配是等價(jià)于用[1, k]的走狀態(tài)機(jī)的模式的走到的串蝴蜓。

為什么這樣是對(duì)的碟绑。舉個(gè)例子我在匹配abc 到c 失敗了，要回退的位置等價(jià)于用bc從頭開始走狀態(tài)機(jī)走到的位置茎匠。（因?yàn)楸┝υ囧e(cuò)下格仲，算法就是這么走的）

再比如如上圖我用ABABC構(gòu)建了DFA狀態(tài)機(jī)。我查詢串是ABABA.... 會(huì)發(fā)現(xiàn)走到第5個(gè)字符失配了诵冒。那么我可以用BABA去重走狀態(tài)機(jī)凯肋，走到的位置等價(jià)于我在第5個(gè)位置失配要走到的位置是一樣的。

image.png

有了這個(gè)觀察之后汽馋，我們就知道我們需要維護(hù)2層狀態(tài)侮东，1層是用0...k，另一層就是用1....k 來(lái)表示上圖的黑線的狀態(tài)機(jī)豹芯。
那么我們?cè)诟律蠄D中J的狀態(tài)機(jī)時(shí)悄雅，第一步繼承的時(shí)候本質(zhì)就是繼承上一層黑線的A轉(zhuǎn)移和B轉(zhuǎn)移。然后更新自己的C轉(zhuǎn)移
就可以寫出構(gòu)造DFA的方法了告组。

char[] cs = str.toCharArray();
int l = cs.length;
int[][] dfa = new int[l][26];
dfa[0][cs[0]-'a'] = 1; // 構(gòu)建初始層
for (int i = 1, pre = 0; i < l;  pre = dfa[pre][cs[i] - 'a'], i++) {
    dfa[i] = dfa[pre].clone(); // 繼承
    dfa[i][cs[i]-'a'] = i+1; // 更新自己
}

綜上我們就介紹完了字符串匹配里的DFA的算法煤伟。
我希望你們可以理解基礎(chǔ)的NEXT ARRAY，然后基于NEXT ARRAY的思想和字符串匹配的暴力解的性質(zhì)木缝，自己推導(dǎo)出DFA的算法便锨。這樣就不容易忘記了。即使忘記我碟，也可以從NEXT ARRAY下手來(lái)回憶放案。

小伙伴可能會(huì)覺得和傳統(tǒng)的KMP算法講解完全不一樣啊。
下面我們來(lái)回歸到其他博客經(jīng)常會(huì)介紹的KMP算法矫俺。

他的本質(zhì)其實(shí)是不確定有限狀態(tài)機(jī)的解法吱殉。又稱NFA掸冤，Nondeterministic finite state
這個(gè)算法是實(shí)現(xiàn)正則表達(dá)式計(jì)算引擎的算法。有興趣的小伙伴可以深入了解友雳，他是怎么被運(yùn)用在正則表達(dá)式解析總的稿湿。

因?yàn)槿绻胗肈FA來(lái)構(gòu)造所有的狀態(tài)轉(zhuǎn)換，狀態(tài)數(shù)量（指數(shù)）過(guò)于龐大押赊。是不可行的饺藤，所以引入的NFA。

4. NFA解法

在NFA解法里流礁，當(dāng)一個(gè)狀態(tài)不匹配時(shí)涕俗，就可能需要多次跳躍。因?yàn)椴荒芰_列所有不匹配的情況神帅。所以只能在狀態(tài)機(jī)里存可能是正確的解的情況再姑。
那么這個(gè)狀態(tài)機(jī)，我們定義為找御，nfa[i] 當(dāng) 查詢串當(dāng)前的索引J 和 匹配串的I 不匹配時(shí)元镀。 匹配串可能和索引J匹配的位置在哪。
那么構(gòu)建初始值必然是nfa[0] = -1萎坷，因?yàn)樵诔跏嘉恢貌黄ヅ浒剂乱粋€(gè)無(wú)論如何回退都是無(wú)法匹配上的，就只能返回-1.
之后的NFA數(shù)組怎么構(gòu)建哆档，我們可以用2個(gè)視角去看蔽挠。這樣可以看的更清晰。

自底向上看

匹配串為char[] pat;瓜浸， 目標(biāo)構(gòu)建int[] nfa;
我們有了0澳淑，我們就要去看nfa[1]怎么構(gòu)建？按照定義我們就需要判斷pat[0]是否和pat[1]相等插佛。如果相等, 那么其實(shí)如果發(fā)生了不匹配, nfa[1] = nfa[0]是一致的杠巡。我們把這個(gè)性質(zhì)稱作匹配可繼承，意思就是如果2個(gè)字符一樣雇寇，我就可以直接使用前一個(gè)的NFA轉(zhuǎn)移來(lái)作為我自己的NFA轉(zhuǎn)移氢拥。

如果不相等。因?yàn)楫?dāng)前pat[1]和一個(gè)字符不匹配了锨侯，那個(gè)字符是有可能和pat[0]匹配的嫩海。所以nfa[1] = 0即可。

當(dāng)為2的時(shí)候囚痴，我們意識(shí)到要想繼續(xù)用匹配可繼承叁怪。 所以之前的J往前回跳的字串，必須得讓大號(hào)索引I 之前的字串都要有深滚。這樣才可以安全的去繼承回跳狀態(tài)奕谭。
那么我們就必須在處理2的問題前,要保證如果0和1的結(jié)尾字符不一樣涣觉，就必須得把0調(diào)整為-1. 來(lái)確保，我們上面提到的性質(zhì)血柳。
那么總結(jié)出來(lái)官册，就是有2個(gè)指針，一個(gè)i指針依次取計(jì)算NFA[I]混驰。 另一個(gè)j指針攀隔，目標(biāo)是使得pat.substring(0, j) == pat.substring(i - j, i)注意JAVA里SUBSTRING函數(shù)是前閉后開的。那么如果pat[j] == pat[i] i++, j++這個(gè)目標(biāo)依然可以滿足栖榨。
但是pat[j] ！= pat[i] 我們就必須調(diào)整J明刷，讓他能夠繼續(xù)滿足pat.substring(0, j) == pat.substring(i - j, i)

在自底向上看的方法里婴栽，我們依賴2個(gè)串的前綴長(zhǎng)度的字符完全一致。好直接繼承使用之前算過(guò)的NFA來(lái)表達(dá)自己未知的NFA辈末。其實(shí)圖簡(jiǎn)單愚争，只要我們每次把J設(shè)置成-1，這個(gè)條件就必然成立了挤聘。但是也就退化成了暴力解法轰枝。所以我們的目標(biāo)是要找到盡可能大的J，滿足pat.substring(0, j) == pat.substring(i - j, i)

所以在我們前一個(gè)定義上我們要加強(qiáng)一下
定義1： nfa[i] 當(dāng) 查詢串當(dāng)前的索引I 和 匹配串的J 不匹配時(shí)组去。 匹配串可能和索引I匹配的位置在哪鞍陨。
定義2： 在眾多的可能位置中，我們希望J 盡可能大

下面我們自頂向下看从隆， 如果調(diào)整J 使得可以找到最大的J

自頂向下看

我們構(gòu)造一個(gè)全局的視角诚撵，假設(shè)有一個(gè)字符串。我們構(gòu)造好了NFA键闺。
當(dāng)它失配的時(shí)候寿烟，我們必須要在NFA里找到下一個(gè)可能的位置去和當(dāng)前失配的字符去比。如果成功辛燥，則可以繼續(xù)往前走筛武。
所以這就必須要求，這個(gè)可能的位置的前面如果有字符挎塌，那么它的所有字符徘六，必然是當(dāng)前這個(gè)查詢串的后綴。我來(lái)畫個(gè)圖勃蜘。

image.png

就是要求藍(lán)色部分的相等是必須保證的硕噩。然后我來(lái)適配這個(gè)新過(guò)來(lái)的字符和當(dāng)前失配的字符是否一致。

所以就有了下面這個(gè)圖缭贡。

image.png

綜上我們可以得出如下代碼。

char[] pat = pattern.toCharArray();
int[] nfa = new int[pat.length];
nfa[0] = -1;
for (int i = 1, j = 0; i < nfa.length; i++, j++) {
// 不變量 assert(pattern.substring(0, j).equals(pattern(i-j, i));
     nfa[i] = (pat[i] == pat[j] ? nfa[j] : j);
     while (j >= 0 && pat[j] != pat[i]) j = nfa[j];
}

有了NFA之后抹竹，在使用這個(gè)數(shù)組的時(shí)候线罕，因?yàn)樗遣淮_定的，所以我們可能要跳多次跳到匹配的字符窃判。有如下代碼：

for (int i = 0, j = 0; j < nfa.length && i < cs.length; i++, j++) {
    while (j >= 0 && pat[j] != cs[i]) j = nfa[j];
}
if (j == nfa.length) return i - j;
return -1;

這里我們?cè)诨赝幌缕渌┛鸵话銜?huì)介紹的NEXT數(shù)組的定義钞楼，其實(shí)就是從J失配，那么NEXT[J]存的就是從i開始的最大前綴長(zhǎng)度能MATCH上pat[j]的后綴袄琳。其實(shí)是有共通性的询件。
我們不妨把文章開頭推薦的博客最后的那個(gè)優(yōu)化過(guò)的KMP NEXT ARRAY求法。換一種方法寫出來(lái)唆樊。
有如下代碼

char[] pat = pattern.toCharArray();
int[] next= new int[pat.length];
next[0] = -1;
int i = 0, j = -1;
while (i < next.length - 1) {
    while (j >= 0 && pat[i] != pat[j]) j = next[j];
    j++;
    i++;
    next[i] =  (pat[i] == pat[j] ? next[j] : j);
}

博客里原始的NEXT ARRAY的求法宛琅。（就是前綴后綴最長(zhǎng)公共元素長(zhǎng)度值向右移動(dòng)一格的數(shù)組）. 因?yàn)橛行╊}目我們是需要知道前綴后綴最長(zhǎng)公共元素長(zhǎng)度值，那么就可以用下述求法逗旁，因?yàn)橄蛴乙苿?dòng)了一格嘿辟。所以我們可以補(bǔ)一個(gè)無(wú)用CHAR在最后。得到全部的前綴后綴最長(zhǎng)公共元素長(zhǎng)度值

char[] pat = pattern.toCharArray();
int[] next= new int[pat.length];
next[0] = -1;
int i = 0, j = -1;
while (i < next.length - 1) {
    while (j >= 0 && pat[i] != pat[j]) j = next[j];
    next[++i] =  ++j;
}

LC 里有很多題痢艺，是基于前綴后綴最長(zhǎng)公共元素來(lái)解的仓洼。
比如

214. Shortest Palindrome
215. Repeated Substring Pattern
216. Longest Happy Prefix
     大多數(shù)題解也解釋的很清楚了，其實(shí)就是算出NEXT數(shù)組后堤舒，利用最大值可以直接或間接得到題目所求色建。

回到上面的代碼，我們不難發(fā)現(xiàn)舌缤，J其實(shí)就是存在I里的箕戳。所以我們可以做進(jìn)一步簡(jiǎn)化。

char[] pat = pattern.toCharArray();
next[0] = -1;
for (int i = 0; i < next.length - 1;) {
    int j = next[i];
    while (j >= 0 && pat[i] != pat[j]) j = next[j];
    next[++i] =  j + 1;
}

AC自動(dòng)機(jī)

做這步簡(jiǎn)化国撵，為的是引出我們的AC自動(dòng)機(jī)的模板陵吸。下面每一行，都是一個(gè)等價(jià)介牙。

KMP這個(gè)狀態(tài)機(jī)轉(zhuǎn)換壮虫，是在一個(gè)匹配串上。如果有一組匹配串，我們就會(huì)用到AC自動(dòng)機(jī)囚似。

我們用一個(gè)CHAR[] 來(lái)存一個(gè)匹配串剩拢。我們可以用一顆TRIE樹來(lái)存一組匹配串。

當(dāng)在TRIE樹中搜索時(shí)饶唤，當(dāng)一個(gè)節(jié)點(diǎn)發(fā)生了失配徐伐。在KMP中，我們用NEXT數(shù)組找到下一個(gè)可能匹配上的節(jié)點(diǎn)募狂。在TRIE樹中办素，我們對(duì)每個(gè)TRIE節(jié)點(diǎn)，都建立一個(gè)NEXT指針祸穷，表示失配的時(shí)候可以跳到哪個(gè)節(jié)點(diǎn)性穿。

在計(jì)算NEXT數(shù)組時(shí)，我們是根據(jù)CHAR[]從前往后粱哼，后面的NEXT[I] 往往依賴于前面的NEXT[J]季二。

在AC自動(dòng)機(jī)中，我們遍歷的是TRIE樹揭措，下層的節(jié)點(diǎn)的NEXT指針依賴于之前層節(jié)點(diǎn)的NEXT指針。所以這里我們需要用BFS來(lái)BUILD AC自動(dòng)機(jī)刻蚯。

我們?cè)诔跏蓟疦EXT數(shù)組時(shí)绊含，NEXT[0] = -1。 我們假設(shè)TRIE樹根節(jié)點(diǎn)為-1炊汹，之后第一層所有孩子的NEXT指針躬充，都指向根節(jié)點(diǎn)。

AC自動(dòng)機(jī)模板

public class ACTemplate {
    class Node {
        Node[] chds = new Node[26];
        Node next = null;
        // other value...
        boolean isWord = false;
    }
    // trie inser template
    void insert(String s) {
        Node p = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (p.chds[idx] == null) p.chds[idx] = new Node();
            p = p.chds[idx];
        }
        // update other value
        p.isWord = true;
    }
    Node root = new Node();
    void buildNextPointer() {
        Queue<Node> q = new LinkedList<>();
        // same as next[0] = -1;
        for (int i = 0; i < 26; i++) {
            if (root.chds[i] == null) continue;
            root.chds[i].next = root;
            q.offer(root.chds[i]);
        }
        while (!q.isEmpty()) {
            Node i = q.poll();
            for (int k = 0; k < 26; k++) {
                Node iPlusOne = i.chds[k]; // iPlusOne = i + 1 in kmp
                if (iPlusOne == null) continue;
                Node j = i.next;
               // same as while (j >= 0 && pat[i] != pat[j]) j = next[j];
                while (j != root && j.chds[k] == null) j = j.next; 
                iPlusOne.next = j.chds[k]; // same as next[i + 1] =  j + 1;
                if (iPlusOne.next == null) iPlusOne.next = root; // avoid NPE
                q.offer(iPlusOne); // for BFS
            }
        }
    }
    int query(String text) {
        char[] cs = text.toCharArray();
        Node j = root;
        int wordCnt = 0;
        for (int i = 0; i < cs.length; i++) {
            int idx = cs[i] - 'a'; 
            // while (j >= 0 && pat[j] != cs[i]) j = nfa[j]; in kmp
            while (j != root && j.chds[idx] == null) j = j.next;
            if (j.chds[idx] == null) continue;
            j = j.chds[idx]; // j++;
            if (j.isWord) {
                wordCnt++;
                j.isWord = false;
            }
        }
        return wordCnt;
    }

    public static void main(String[] args) {
        String text = "yasherhs";
        String[] words = {"she", "her", "say", "shr","rh"};
        ACTemplate acTemplate = new ACTemplate();
        for (String w : words) acTemplate.insert(w);
        acTemplate.buildNextPointer();
        System.out.println(acTemplate.query(text));
        // should be 3
    }
}

鑒于目前LC 還沒有出過(guò)需要用到AC自動(dòng)機(jī)的題目讨便，所以就只簡(jiǎn)單給一個(gè)模板充甚。模板中我們維護(hù)了節(jié)點(diǎn)是否為單詞的信息。最后用來(lái)統(tǒng)計(jì)所有單詞個(gè)數(shù)霸褒。不同題目要統(tǒng)計(jì)的信息不同伴找，可能會(huì)改變NODE節(jié)點(diǎn)里存的信息不同。等之后有題目進(jìn)來(lái)废菱，我再過(guò)來(lái)更新技矮。

總結(jié)

其實(shí)這篇文章主要是要講KMP，然后怎么從KMP映射到AC自動(dòng)機(jī)的擴(kuò)展殊轴。

在 KMP中衰倦。我們從NEXT 數(shù)組的思想映射到DFA的KMP解法。

再擴(kuò)展到NFA的KMP解法旁理。本質(zhì)是2點(diǎn)樊零。

1. 不變量的維護(hù)，每一次I進(jìn)來(lái)孽文，都必須有str.substring(0, j) == str(i - j, i)驻襟。
2. nfa里存的值要盡可能大夺艰。
   有了第一個(gè)性質(zhì)。我們就可以寫出nfa[i] = pat[i] == pat[j] ? nfa[j] : j;
   這個(gè)代碼塑悼。
   我們假設(shè)第二個(gè)性質(zhì)存在劲适，（自底向上可以數(shù)學(xué)歸納，證明0是對(duì)的厢蒜。之后假設(shè)K對(duì)霞势，K+1必對(duì)）所以我們可以假設(shè)nfa[k] 能返回盡可能大的值，然后我們貪心的找到J最大的位置斑鸦。來(lái)維護(hù)下次循環(huán)時(shí)的第一個(gè)特性
   就有了如下代碼while (j >= 0 && pat[i] != pat[j]) j = nfa[j];

LEETCODE 有很多題目是基于前綴后綴最大公共長(zhǎng)度值的愕贡，所以我們只要把第一個(gè)性質(zhì)退化成nfa[i] = j;， 然后最后補(bǔ)一個(gè)無(wú)用字母巷屿。就可以得到這個(gè)原始NEXT數(shù)組固以。

AC自動(dòng)機(jī)就是建TRIE樹, BFS根據(jù)KMP的模板改出BUILD_NEXT_POINTER的代碼即可。

小伙伴可以拿LeetCode 28. Implement strStr() 來(lái)練習(xí)KMP模板嘱巾。DFA解法

    public int strStr(String haystack, String pattern) {
        char[] pat = pattern.toCharArray(), cs = haystack.toCharArray();
        if (pat.length == 0) return 0;
        int[][] dfa = new int[pat.length][256];
        dfa[0][pat[0]] = 1;
        for (int i = 1, pre = 0; i < pat.length; i++) {
            dfa[i] = dfa[pre].clone();
            dfa[i][pat[i]] = i + 1;
            pre = dfa[pre][pat[i]];
        }
        int j = 0, i = 0;
        for (; i < cs.length && j < pat.length; i++) {
            j = dfa[j][cs[i]];
        }
        if (j == pat.length) return i - j;
        return -1;
    }