1.字符串總結。 通過了這幾天的字符串的學習，我所學習的字符串的內容大致有，前綴樹， 哈希，kmp算法，ac自動機等內容。 Hash就是一個散列表，通過壓縮映射存關鍵信息，需要掌握的就是處理字符串的算法以及處理沖突，在這當中，還要運用到前向星，以及數據結構的知識，在處理字符串時還要涉及一些數學方面的東西， Hash表建立的時間復雜度是O（n）， 而查找的時間復雜度是o（1）。我覺得Hash我用得并不是太順手，我用的更多的是Trie前綴樹。 Trie前綴樹是一個保存字符串的集合，相比于hash表，它顯得更好用并且更省空間，因為它是用前向星存儲，通過樹的dfs遍歷來存儲字符串，后面的ac自動機就是在trie樹上面存的。Trie前綴樹的建立運用了在學習數據結構時用指針建樹的知識，用dfs建立一棵樹，它的大致流程是： 1． 定義一個結構體，包含的成員有：一個大小為26的數組，一個count來記錄每個節點連接到根節點的單詞的個數，在對結構體定義一個根的指針。 2． 從根節點開始建立，如果該單詞當前字母在樹的當前層存在，就進入該節點，以此類推，如果該節點沒有被訪問過，那就建立一個節點，當到達該單詞最后一個字母，在建立的節點的count值加一，這樣做是因為，如果有一個單詞與當前單詞一樣，那也能記錄下來。這樣就使后面的訪問變得更加方便。 3． 在字典書中查找一某個單詞為前綴的單詞的個數那就簡單多了， 只需要像建立trie樹那樣一個字母一個字母的找，只不過如果發現該字母在樹中不存在，就要返回一個錯誤信息，而不是建立節點，如果把需要查找的單詞的每一個字母都找完了，那就要返回count值，因為要考慮有兩個單詞相同的情況，count的作用就表現出來了。 總的來說，我覺得trie我掌握的還不錯，相比于hash，我更喜好于用trie樹。 KMP算法。在我的腦海中，KMP就是一直跳的算法，相比于老老實實的一個字母一個字母的匹配，它顯得更勝一籌。對于小于26的字符，還看不出它的優點，而在大的字符串面前，他就優秀了，因為必然有多個字符相同（抽屜原理），所以它十分的省時間，在這當中，也用到了一些關于前綴的知識，通俗地講，就是把從字符串第一位開始到后面某一位作為一個基準，這就引入了一個next數組，它記錄了從當前位置到前面某個位置與前面提到的基準比較，匹配的位置，這個過程實現的難度也比較低，來看看大致流程： 1. 它分為兩步，第一步就是建立next數組，這個有個關鍵，就是next數組的初始化，定義 next[0] = -1。第一步就是定義兩個變量i，j，來模擬指針的作用，i初值為0，j初值為-1，以一個while語句作為大的循環，作用是讓i指針只訪問整個字符串，再循環內，如果i，與j所在的字母相等或者j在初始值，那么i++，j++，next[i] = j，否則就把j跳到next[j]; 2. 第二步就是匹配兩個字符串，與第一步極為類似，就是第一步中的i指針指的是被匹配字符串并且i，j都要初始化為0，而這一步應該把i指向匹配的字符串，這一步還要加上一個if來判斷j是否訪問完了被匹配的字符串，如果是，那就打印或者返回，j就跳到next[j]；對于KMP算法有一些變式，如布條上最多能剪多少花，這樣如果使用裸的KMP，那就包含了重復的部分，就要報錯，就要在上面加黑字體那一步處做改動，j直接跳回-1； KMP算法的復雜度為o（m）預處理，o（n）匹配，所以加起來要o（m+n），KMP對1個匹配1個很有效，但是對多個就顯得力不從心了，這時就要使用到AC自動機了。 AC自動機，剛學習ac自動機時，還真的以為能自動ac，ac自動機就是一種匹配多個字符串的高效的方法，如果要靠kmp來解決問題，那就要考k個n＋m，這個太浪費時間，寫寫暴力還行，不能拿全分，但是想一想，他浪費時間浪費在每個字符串都要單個的求next數組，單個的與文章匹配，我們想一想，如果我們把這些單個化為一個整體，那就節省時間了，把字符串結合在一起的方法有很多，比如什么hash，trie樹，而ac自動機就是建立在trie樹上面的，而原來KMP的next數組變成了樹的fail指針，流程其實挺簡單的，由于細節在trie樹和kmp已分析過，所以大概分析一下，建樹還是一如既往。要加一個set_fail函數來查找每個節點的fail，這個過程要說一下，就是fail一直跳，知道不為空的節點或根，在把fail指向節點或根，這樣做原因是什么？想想并查集，它的一個優化就是直接接一根線到祖先（路徑壓縮），可能有異曲同工之妙啊，接了fail的先以后就要做做后一步了，把文章放到自動機上跑一邊，就是和trie找前綴過程有點像，總之，ac自動機作用相當打，在kmp上更上一層樓。下面配上代碼。