一.基本演算法:
枚舉. (poj1753,poj2965)
貪心(poj1328,poj2109,poj2586)
遞歸和分治法.
遞推.
構造法.(poj3295)
模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖演算法:
圖的深度優先遍歷和廣度優先遍歷.
最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓撲排序 (poj1094)
二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)
最大流的增廣路演算法(KM演算法). (poj1459,poj3436)
三.數據結構.
串 (poj1035,poj3080,poj1936)
排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)
簡單並查集的應用.
哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼樹(poj3253)
堆
trie樹(靜態建樹、動態建樹) (poj2513)
四.簡單搜索
深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動態規劃
背包問題. (poj1837,poj1276)
型如下表的簡單DP(可參考lrj的書 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學
組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.
幾何公式.
叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)
多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)
中級（校賽壓軸及省賽中等難度）:
一.基本演算法:
C++的標准模版庫的應用. (poj3096,poj3007)
較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖演算法:
差分約束系統的建立和求解. (poj1201,poj2983)
最小費用最大流(poj2516,poj2516,poj2195)
雙連通分量(poj2942)
強連通分支及其縮點.(poj2186)
圖的割邊和割點(poj3352)
最小割模型、網路流規約(poj3308)
三.數據結構.
線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)
靜態二叉檢索樹. (poj2482,poj2352)
樹狀樹組(poj1195,poj3321)
RMQ. (poj3264,poj3368)
並查集的高級應用. (poj1703,2492)
KMP演算法. (poj1961,poj2406)
四.搜索
最優化剪枝和可行性剪枝
搜索的技巧和優化 (poj3411,poj1724)
記憶化搜索(poj3373,poj1691)
五.動態規劃
較為復雜的動態規劃(如動態規劃解特別的旅行商TSP問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)
樹型動態規劃(poj2057,poj1947,poj2486,poj3140)
六.數學
組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.
數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
隨機化演算法(poj3318,poj2454)
雜題(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.
坐標離散化.
掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多邊形的內核(半平面交)(poj3130,poj3335)
幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)
高級（regional中等難度）:
一.基本演算法要求:
代碼快速寫成,精簡但不失風格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
保證正確性和高效性. poj3434
二.圖演算法:
度限制最小生成樹和第K最短路. (poj1639)
最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最優比率生成樹. (poj2728)
最小樹形圖(poj3164)
次小生成樹.
無向圖、有向圖的最小環
三.數據結構.
trie圖的建立和應用. (poj2778)
LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法(RMQ+dfs)).(poj1330)
雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的目的). (poj2823)
左偏樹(可合並堆).
後綴樹(非常有用的數據結構,也是賽區考題的熱點).(poj3415,poj3294)
四.搜索
較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)
五.動態規劃
需要用數據結構優化的動態規劃.(poj2754,poj3378,poj3017)
四邊形不等式理論.
較難的狀態DP(poj3133)
六.數學
組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.
半平面求交(poj3384,poj2540)
可視圖的建立(poj2966)
點集最小圓覆蓋.
對踵點(poj2079)
⑵ 那些經典演算法：AC自動機
第一次看到這個名字的時候覺得非常高級，深入學習就發現，AC就是一種多模式字元串匹配演算法。前面介紹的BF演算法，RK演算法，BM演算法，KMP演算法都屬於單模式匹配演算法，而Trie樹是多模式匹配演算法，多模式匹配演算法就是在一個主串中查找多個模式串，舉個最常用的例子，比如我們在論壇發表評論或發帖的時候，一般論壇後台會檢測我們發的內容是否有敏感詞，如果有敏感詞要麼是用***替換，要麼是不讓你發送，我們評論是通常是一段話，這些敏感詞可能成千上萬，如果用每個敏感詞都在評論的內容中查找，效率會非常低，AC自動機中，主串會與所有的模式串同時匹配，這時候就可以利用AC自動機這種多模式匹配演算法來完成高效的匹配，
AC自動機演算法是構造一個Trie樹，然後再添加額外的失配指針。這些額外的適配指針准許在查找字元串失敗的時候進行回退（例如在Trie樹種查找單詞bef失敗後，但是在Trie樹種存中bea這個單詞，失配指針會指向前綴be），轉向某些前綴分支，免於重復匹配前綴，提高演算法效率。
常見於IDS軟體或病毒檢測軟體中病毒特徵字元串，可以構建AC自動機，在這種情況下，演算法的時間復雜度為輸入字元串的長度和匹配數量之和。
假設現有模式字元串集合：{abd,abdk, abchijn, chnit, ijabdf, ijaij} 構建AC自動機如下：
說明：
1）當前指針curr指向AC自動機的根節點：curr=root。
2）從文本串中讀取（下）一個字元。
3）從當前節點的所有孩子節點中尋找與該字元匹配的節點：
4）若fail == null，則說明沒有任何子串為輸入字元串的前綴，這時設置curr = root，執行步驟2.
若fail != null,則將curr指向 fail節點，指向步驟3。
理解起來比較復雜，找網上的一個例子，假設文本串text = 「abchnijabdfk」。
查找過程如下：
說明如下：
1）按照字元串順序依次遍歷到：a-->b-->c-->h ,這時候發現文本串中下一個節點n和Trie樹中下一個節點i不匹配，且h的fail指針非空，跳轉到Trie樹中ch位置。
注意c-->h的時候判斷h不為結束節點，且c的fail指針也不是結束節點。
2）再接著遍歷n-->i,發現i節點在Trie樹中的下一個節點找不到j，且有fail指針，則繼續遍歷，
遍歷到d的時候要注意，d的下一個匹配節點f是結束字元，所以得到匹配字元串：ijabdf，且d的fail節點也是d，且也是結束字元，所以得到匹配字元串abd，不過不是失敗的匹配，所以curr不跳轉。
先將目標字元串插入到Trie樹種，然後通過廣度有限遍歷為每個節點的所有孩子節點找到正確的fail指針。
具體步驟如下：
1）將根節點的所有孩子節點的fail指針指向根節點，然後將根節點的所有孩子節點依次入隊列。
2）若隊列不為空：
2.1）出列一個字元，將出列的節點記為curr，failTo表示curr的
fail指針，即failTo = curr.fail 。
2.2) 判斷curr.child[i] == failTo.child[i]是不是成立：
成立：curr.child[i].fail = failTo.child[i]
因為當前字元串的後綴和Tire樹的前綴最長部分是到fail，
且子字元和failTo的下一個字元相同，則fail指針就是
failTo.child[i]。
不成立： 判斷failTo是不是為null是否成立：
成立： curr.child[i].fail = root = null。
不成立： failTo = failTo.fail 繼續2.2
curr.child[i]入列，再次執行步驟2）。
3）隊列為空結束。
每個結點的fail指向的解決順序是按照廣度有限遍歷的順序完成的，或者說層序遍歷的順序進行，我們根據父結點的fail指針來求當前節點的fail指針。
上圖為例，我們要解決y節點的fail指針問題，已經知道y節點的父節點x1的fail是指向x2的，根據fail指針的定義，我們知道紅色橢圓中的字元串序列肯定相等，而且是最長的公共部分。依據y.fail的含義，如果x2的某個孩子節點和節點y表示的表示的字元相等，y的fail就指向它。
如果x2的孩子節點中不存在節點y表示的字元。由於x2.fail指向x3，根據x2.fail的含義，我們知道綠色框中的字元序列是相同的。顯然如果x3的某個孩子和節點y表示字元相等，則y.fail就指向它。
如果x3的孩子節點不存在節點y表示的字元，我們重復這個步驟，直到xi的fail節點指向null，說明我們達到頂層，只要y.fail= root就可以了。
構造過程就是知道當前節點的最長公共前綴的情況下，去確定孩子節點的最長公共前綴。
下圖中，每個節點都有fail虛線，指向根節點的虛線沒畫出，求圖中c的孩子節點h的fail指向：
原圖中，深藍色的框出來的是已經確定fail指針的，求紅色框中h節點的fail指針。
這時候，我們看下h的父親節點c的fail指針指向，為ch中的c（這表示abc字元串的所有後綴bc和c和Trie樹的所有前綴中最長公共部分為c），且這個c節點的孩子節點中有字元為h的字元，所以圖中紅色框中框出的h節點的fail指針指向 ch字元串中的h。
求紅色框中i的fail指針指向，上圖中，我們可以看到i的父親節點h的指向為ch中的h，（也就是說我們的目標字元串結合中所有前綴和字元序列abch的所有後綴在Trie樹中最長前綴為ch。）我們比較i節點和ch中的h的所有子節點，發現h只有一個n的子節點，所以沒辦法匹配，那就繼續找ch中h的fail指針，圖中沒畫出，那麼就是它的fail指針就是root，然後去看root所有子節點中有沒有和i相等的，發現最右邊的i是和我們要找的i相等的，所以我們就把i的fail指針指向i，如後面的圖。
⑶ DPDK ACL演算法介紹
DPDK提供了三種classify演算法：最長匹配LPM、精確匹配（Exact Match）和通配符匹配（ACL）。
其中的ACL演算法，本質是步長為8的Multi-Bit Trie，即每次可匹配一個位元組。一般來說步長為n時，Trie中每個節點的出邊為2^n，但DPDK在生成run-time structures時，採用DFA/QRANGE/SINGLE這幾種不同的方式進行數據結構的壓縮，有效去除了冗餘的出邊。本文將為大家介紹ACL演算法的基本原理，主要內容包括：trie樹的構造、運行時的node array生成和匹配原理。對於ACL介面的使用，參考DPDK的官方文檔即可。
ACL規則主要面向的是IP流量中的五元組信息，即IP/PORT/PROTO，演算法在這個基礎上進行了抽象，提供了三種類型的匹配區域：
熟悉這三種類型的使用後，完全可以用它們去匹配網路報文的其它區域，甚至將其應用到其它場景中。
具體來說，rte_acl_field_def有5個成員：type、size、field_index、input_index、offset。
如果要深入理解演算法，可以思考這幾個欄位的意義，或者換個角度來看：
對於規則的定義，要注意如下兩點：
比如定義了5個field，那麼請給出每一個的具體定義：
像field[1]中IP和mask都為0，表示匹配所有的IP地址；field[3]中range由0到65535，表示匹配所有。類似這樣的全匹配一定要顯示的定義出來，因為如果不明確定義，這些欄位的值取決於編譯器的，最後編譯的ACL規則很可能與原有設想存在偏差。
如果在規則中，對於某個field不進行限制，對於不同type的field，規則書寫時有一定差異：
對於BITMASK和MASK類型，全0代表匹配所有，如上例中的field[0]、field[1]；
對於RANGE，則按照上述field[3]中的形式定義。
規則定義好後，會轉換為trie樹並最終合並到一起。
實際處理過程中，build_trie函數會自底向上的將rule中的每個field轉換為node，然後將這些node合並生成這條rule的trie，最後將這個trie與已有的trie進行merge，最終生成整個rule set的trie。
tire由node組成，其主要數據成員如下：
node中values成員用於記錄匹配信息，ptrs則用於描述node的出邊，用於指向轉換後的node。
values採用bitmap進行壓縮，其數據結構為struct rte_acl_bitset values; 一個byte取值范圍是[0,255]，可通過256個bit位來進行對應，並實現byte值的快速查找：即通過第x位的bit值是否為1來判斷是否包含數值x（0 <= x < 256）。
num_ptrs用於描述出邊數目，ptrs即為實際的出邊，它記錄了其匹配值values和匹配後的節點指針。
match_flag和mrt則用於記錄匹配結果，trie樹中葉子節點一定是記錄匹配結果的節點。
trie樹其詳細結構比較復雜，這里將其結構進行簡化，如下所示：
上圖的trie樹有4個node，通過ptrs進行指向，values欄位為匹配值的bitmap表示，為了表述的簡潔，後續會採用simple的方式進行描述。
在trie simple中，實心節點表示匹配節點，邊上的數字代表匹配值（為便於閱讀，採用實際值而不再是bitmap形式），…代表其它匹配值。
不同type的field，轉換為node的方式會有所不同。
目前提供的3種類型：BITMASK描述一個byte的匹配，支持mask模式；MASK用於描述4個byte的匹配，支持mask模式；RANGE描述2個byte的匹配，此時mask表示上限。
field到node的轉換，見build_trie中的for循環，具體轉換函數則參考：
對於BITMASK，如{.value.u8 = 6, .mask_range.u8 = 0xff,}，它最後的轉換形式如下：
構造field的node時，總會在結尾添加一個空的end節點，最後一個field除外（它是match node）。在for循環中每完成了一個field的解析後，會將其合並到root中，從而生成這個rule的trie。
合並前，也會先構造一個空的end node（見build_trie函數中，while循環下的root創建），讓它與field構成的node頭合並，因為不相交，所以merge時會將匹配信息合並到end node並釋放原有的頭，並將field鏈的end節點返回（保存到end_prev中），下次合並時，就用此end節點與新的node頭合並。
循環遍歷完所有的field後，這些node就串聯起來了，構成這個rule的trie。
對於多個rule，每次構造完成後會merge到整體的trie中。
這里詳細介紹下merge演算法原理，其實仔細閱讀acl_merge_trie函數的注釋即可。
對於node A和node B的merge， acl_merge_trie函數返回一個節點，這個節點指向它們路徑的交集。
這里給出三個例子用於展示merge前後的變化。為了減少狀態點，構造rte_acl_field_def如下：
示例1：
acl_rules[1]為trie A，acl_rules[0]對應trie B，最終trie B合並到trie A上，具體如下：
1和1』合並時，因為level為0，所以1』直接合並到1中；
4和4』合並時，因為節點無交集，所以創建新節點c1(node 4的拷貝)，並將4'上的邊拷貝到c1中。
示例2，rule類別相同，但優先順序不同：
acl_rules[1]為trie A，acl_rules[0]對應trie B，最終trie B合並到trie A上，具體如下：
6和6』是match node，類別相同，且6的優先順序為2大於6』的優先順序。
6和6』合並時，直接返回6。而前面創建的新節點，如d1，已包含5』的所有邊（非ACL_INTERSECT_B），所以最終返回5，free d1。
同理依次往上回溯，a4，b3，c2，也依次被釋放，最終merge的trie即為原來的trie A。
示例3，rule類別不同，優先順序相同：
acl_rules[1]為trie A，acl_rules[0]對應trie B，最終trie B合並到trie A上，具體如下：
6和6』是match node，因為類別不同，所以最終創建了新node e1，這也導致示例3和示例2最終merge結果的不同。
合並是一個遞歸的過程，逆向思考構造過程會有助於理解演算法。另外，在build_trie之前會sort_rule，匹配范圍更大的rule會放到前面優先構造trie，個人為這樣node A包含node B的概率更大，這可能也是merge時創建的node C是A的拷貝而不是B的拷貝的原因，因為這樣出現ACL_INTERSECT_B的概率相對較低。
一些說明：
trie樹構造完成後，會將其由指針跳轉的形式轉換為等效的數組索引形式，即node array，既可讓匹配數據更緊湊，也可提高匹配演算法的效率。
採用node array的方式進行狀態點的壓縮是很常見的優化方式，比如snort裡面的ac演算法(acsmx.c)：
筆者也曾經做過類似的優化，通過將出邊由指針方式修改為索引方式，整個匹配tree的內存佔用只需要原來的1/5。
將指針方式轉換為node array形式是優化的第一步，對於Next[256]出邊又可以採用多種壓縮方式，比如snort中新的ac演算法(acsmx2.c)，就採用了Sparse rows和Banded rows等多種壓縮方式，但其原理是將出邊進行映射轉換，本質上還是做DFA狀態跳轉。
DPDK對邊的壓縮方式與上述類似，不過它優化的粒度更細，不同type的node有不同的壓縮方式：
比如在示例三中，node 1為DFA節點（根節點強制使用DFA方式），2、3、a5、b4、c3、d2為QRANGE，4、5為SINGLE，6、e1為MATCH。
2、3、a5、b4雖然在圖上僅有一條有效邊，但它不為SINGLE，因為對於無效的匹配其實也會有出邊，所以它的真實出邊數目並不唯一，只有像4、5這類全匹配節點才是真正的SINGLE節點。
在構造node array前，會調用acl_calc_counts_indices函數更新node的node type，fanout等信息。
node type依據其fanout值決定，fanout計算見acl_count_fanout函數，其原理是：
比如對於示例3中的d2節點：
fanout計算完成後，若其值為1則為SINGLE節點，(1, 5]為QRANGE節點，(5, 256]為DFA節點。
注意：對於trie樹的root節點，不論fanout值為多少，會強制將其構造為DFA節點，且其fanout值會重新計算。
type和fanout計算完成後，會統計各類節點數目，信息保存在acl_calc_counts_indices傳入的counts參數中，隨後rte_acl_gen依據這些信息將整塊的node array內存分配出來，其布局大致如下：
Data indexes中用於保存在rte_acl_field_def中定義的offset；
Results對應match node，用於保存匹配結果。
Trans table包含整個匹配過程中的跳轉點：
靜態將整塊node array分配完成後，就需要依據trie 樹的node信息填充Trans table和Results了，具體過程見acl_gen_node函數；Data indexes的填充則在acl_set_data_indexes中完成。
2.2中的內存布局大致描繪了各種類型節點的分布情況，DFAs內部由一個一個的DFA節點組成，QUADs和SINGLEs也一樣，都是由相同類型的節點構成。
對於每一個節點，其結構則類似如下形式：
DFA節點的fanout一般為4，出邊數為fanout*RTE_ACL_DFA_GR64_SIZE；（圖中畫的為fanout為4的情況，256條出邊）
QUAD節點的fanout不超過5，即為節點的出邊數不超過5；（圖中畫的為fanout為4的情況）
SINGLE節點只有一個出邊；
圖中的trans即為這個節點的出邊，它本質是一個uint64的數據結構，通過trans和input信息即可計算得到下一個節點的index，從而實現匹配跳轉。trans中不同bit位包含著豐富的信息，具體見acl.h中的說明即可。
高32位對於不同類型的節點有不同的解釋：
低32位：
在實際處理過程中，通過高32位與input_byte計算得到index，與低32位中的addr，即可快速定位到下一個trans：trans_table + (addr+index)。
這里的處理其實與傳統的DFA跳轉差別很大，傳統處理時，next = node[『input』]，跳轉到下一個節點，然後採用next[『input』]進行跳轉和匹配，即使有數據結構的壓縮，跳轉目標仍是狀態點。但DPDK中，跳轉時直接採用trans_table + (addr+index)，直接找到了狀態點的邊（trans），而不是到狀態點。
跳轉表具體構建時，採用acl_gen_node函數完成：
匹配的過程與跳轉表的構建其實是互為一體的，如何構建跳轉表就決定了如何進行匹配。
在2.3節，對於跳轉的形式已進行了說明，具體可閱讀rte_acl_classify_scalar函數：跳轉時直接採用trans_table + (addr+index)，直接找到了狀態點的邊（trans），而不是到狀態點。
對於具體的匹配過程，還有一點需要注意，即GET_NEXT_4BYTES的使用，每次匹配時候都會去4BTYTES進行匹配，這也是為什麼定義input fields時要求4位元組連續。比如我在dpdk-dev郵件組中問的這個 問題 。
解決4位元組連續，可以通過定義相同的input_index來解決，比如像郵件中提到的設置sport/dport的input_index相同，這是因為data indexes的構造取決於input_index，見acl_build_index函數；同時field_index不同、input_index相同時可避免對field區間的優化（如果優化，將某個field去掉了，這時4位元組匹配會失效）。郵件中的問題，正是因為field[3]被優化掉後，4位元組連續匹配出現問題。
在特定的場合還必須通過指定.size為32來解決，即使type類型為BITMASK，見DPDK的ACL文檔中關於 tos示例的說明 。
另外再說下field_index，前面提出一個問題：field_index是否多餘？
答案是不多餘，因為演算法中會對field進行優化，如果不指定field_index欄位，這個優化就無法進行了，具體的優化處理見acl_rule_stats函數。
優化過程中要進行input_index的判斷，這是因為相同的input_index可以有多個field，但其中只有某個field是completely wild時應避免進行優化。只有相同input_index的所有field都是completely wild時，才應該將這個field優化掉。
上面的一系列說明，都是針對GET_NEXT_4BYTES每次匹配四個位元組的匹配進行的補充說明。
匹配的具體過程，這里用圖形的方式進行簡要說明，為了能有多種類型的node，這里構造規則如下：
trie樹如下所述：
對應的node array如下圖所示：
假設輸入數據為：proto 16, ip 192.12.8.8，則transition跳轉方式如上圖紅線所示：
注意：node array中indexes、DFA0和idle省略了。
關於trie樹相關的理論知識參考 這里 。
本文主要介紹了DPDK的ACL演算法，詳細描述了如何由規則生成trie，並將trie轉換為node array的過程，在文末通過示例介紹了具體的匹配過程。文章旨在介紹ACL演算法的基本思路，希望對大家能有所幫助。
⑷ Android socket源碼解析(三)socket的connect源碼解析
上一篇文章著重的聊了socket服務端的bind，listen，accpet的邏輯。本文來著重聊聊connect都做了什麼？
如果遇到什麼問題，可以來本文 https://www.jianshu.com/p/da6089fdcfe1 下討論
當服務端一切都准備好了。客戶端就會嘗試的通過 connect 系統調用，嘗試的和服務端建立遠程連接。
首先校驗當前socket中是否有正確的目標地址。然後獲取IP地址和埠調用 connectToAddress 。
在這個方法中，能看到有一個 NetHooks 跟蹤socket的調用，也能看到 BlockGuard 跟蹤了socket的connect調用。因此可以hook這兩個地方跟蹤socket，不過很少用就是了。
核心方法是 socketConnect 方法，這個方法就是調用 IoBridge.connect 方法。同理也會調用到jni中。
能看到也是調用了 connect 系統調用。
文件：/ net / ipv4 / af_inet.c
在這個方法中做的事情如下：
注意 sk_prot 所指向的方法是， tcp_prot 中 connect 所指向的方法，也就是指 tcp_v4_connect .
文件：/ net / ipv4 / tcp_ipv4.c
本質上核心任務有三件:
想要能夠理解下文內容，先要明白什麼是路由表。
路由表分為兩大類：
每個路由器都有一個路由表(RIB)和轉發表 (fib表)，路由表用於決策路由，轉發表決策轉發分組。下文會接觸到這兩種表。
這兩個表有什麼區別呢？
網上雖然給了如下的定義：
但實際上在Linux 3.8.1中並沒有明確的區分。整個路由相關的邏輯都是使用了fib轉發表承擔的。
先來看看幾個和FIB轉發表相關的核心結構體：
熟悉Linux命令朋友一定就能認出這裡面大部分的欄位都可以通過route命令查找到。
命令執行結果如下：
在這route命令結果的欄位實際上都對應上了結構體中的欄位含義：
知道路由表的的內容後。再來FIB轉發表的內容。實際上從下面的源碼其實可以得知，路由表的獲取，實際上是先從fib轉發表的路由字典樹獲取到後在同感加工獲得路由表對象。
轉發表的內容就更加簡單
還記得在之前總結的ip地址的結構嗎？
需要進行一次tcp的通信，意味著需要把ip報文准備好。因此需要決定源ip地址和目標IP地址。目標ip地址在之前通過netd查詢到了，此時需要得到本地發送的源ip地址。
然而在實際情況下，往往是面對如下這么情況：公網一個對外的ip地址，而內網會被映射成多個不同內網的ip地址。而這個過程就是通過DDNS動態的在內存中進行更新。
因此 ip_route_connect 實際上就是選擇一個緩存好的，通過DDNS設置好的內網ip地址並找到作為結果返回，將會在之後發送包的時候填入這些存在結果信息。而查詢內網ip地址的過程，可以成為RTNetLink。
在Linux中有一個常用的命令 ifconfig 也可以實現類似增加一個內網ip地址的功能：
比如說為網卡eth0增加一個IPV6的地址。而這個過程實際上就是調用了devinet內核模塊設定好的添加新ip地址方式，並在回調中把該ip地址刷新到內存中。
注意 devinet 和 RTNetLink 嚴格來說不是一個存在同一個模塊。雖然都是使用 rtnl_register 注冊方法到rtnl模塊中：
文件：/ net / ipv4 / devinet.c
文件：/ net / ipv4 / route.c
實際上整個route模塊，是跟著ipv4 內核模塊一起初始化好的。能看到其中就根據不同的rtnl操作符號注冊了對應不同的方法。
整個DDNS的工作流程大體如下：
當然，在tcp三次握手執行之前，需要得到當前的源地址，那麼就需要通過rtnl進行查詢內存中分配的ip。
文件：/ include / net / route.h
這個方法核心就是 __ip_route_output_key .當目的地址或者源地址有其一為空，則會調用 __ip_route_output_key 填充ip地址。目的地址為空說明可能是在回環鏈路中通信，如果源地址為空，那個說明可能往目的地址通信需要填充本地被DDNS分配好的內網地址。
在這個方法中核心還是調用了 flowi4_init_output 進行flowi4結構體的初始化。
文件：/ include / net / flow.h
能看到這個過程把數據中的源地址，目的地址，源地址埠和目的地址埠，協議類型等數據給記錄下來，之後內網ip地址的查詢與更新就會頻繁的和這個結構體進行交互。
能看到實際上 flowi4 是一個用於承載數據的臨時結構體，包含了本次路由操作需要的數據。
執行的事務如下：
想要弄清楚ip路由表的核心邏輯，必須明白路由表的幾個核心的數據結構。當然網上搜索到的和本文很可能大為不同。本文是基於LInux 內核3.1.8.之後的設計幾乎都沿用這一套。
而內核將路由表進行大規模的重新設計，很大一部分的原因是網路環境日益龐大且復雜。需要全新的方式進行優化管理系統中的路由表。
下面是fib_table 路由表所涉及的數據結構：
依次從最外層的結構體介紹：
能看到路由表的存儲實際上通過字典樹的數據結構壓縮實現的。但是和常見的字典樹有點區別，這種特殊的字典樹稱為LC-trie 快速路由查找演算法。
這一篇文章對於快速路由查找演算法的理解寫的很不錯: https://blog.csdn.net/dog250/article/details/6596046
首先理解字典樹：字典樹簡單的來說，就是把一串數據化為二進制格式，根據左0，右1的方式構成的。
如圖下所示：
這個過程用圖來展示，就是沿著字典樹路徑不斷向下讀，比如依次讀取abd節點就能得到00這個數字。依次讀取abeh就能得到010這個數字。
說到底這種方式只是存儲數據的一種方式。而使用數的好處就能很輕易的找到公共前綴，在字典樹中找到公共最大子樹，也就找到了公共前綴。
而LC-trie 則是在這之上做了壓縮優化處理，想要理解這個演算法，必須要明白在 tnode 中存在兩個十分核心的數據：
這負責什麼事情呢？下面就簡單說說整個lc-trie的演算法就能明白了。
當然先來看看方法 __ip_dev_find 是如何查找
文件：/ net / ipv4 / fib_trie.c
整個方法就是通過 tkey_extract_bits 生成tnode中對應的葉子節點所在index，從而通過 tnode_get_child_rcu 拿到tnode節點中index所對應的數組中獲取葉下一級別的tnode或者葉子結點。
其中查找index最為核心方法如上，這個過程，先通過key左移動pos個位，再向右邊移動（32 - bits）演算法找到對應index。
在這里能對路由壓縮演算法有一定的理解即可，本文重點不在這里。當從路由樹中找到了結果就返回 fib_result 結構體。
查詢的結果最為核心的就是 fib_table 路由表，存儲了真正的路由轉發信息
文件：/ net / ipv4 / route.c
這個方法做的事情很簡單，本質上就是想要找到這個路由的下一跳是哪裡？
在這裡面有一個核心的結構體名為 fib_nh_exception 。這個是指fib表中去往目的地址情況下最理想的下一跳的地址。
而這個結構體在上一個方法通過 find_exception 獲得.遍歷從 fib_result 獲取到 fib_nh 結構體中的 nh_exceptions 鏈表。從這鏈表中找到一模一樣的目的地址並返回得到的。
文件：/ net / ipv4 / tcp_output.c
⑸ 請教一個關於二維數組的演算法
如果僅僅對於6×9這么小的矩陣來說，可以直接循環尋找各個方向的匹配，源代碼如下:
#include <cstdio>
#include <cstring>
using namespace std;
int Array[6][9] =
{
{1,1,0,1,0,0,1,0,0},
{4,1,1,0,0,0,1,4,0},
{4,0,0,1,1,4,4,1,0},
{0,0,0,0,0,1,0,1,0},
{0,0,1,1,4,1,0,1,0},
{0,0,0,0,4,0,0,0,0},
};
int mo[5] = {1,1,4,1,1};
bool check_right(int a,int b) //右方向
{
int i;
for (i=0;i<5;i++) if (b + i >= 9) return false;
else if (Array[a][b + i] != mo[i]) return false;
return true;
}
bool check_down(int a,int b) //下方向
{
int i;
for (i=0;i<5;i++) if (a + i >= 6) return false;
else if (Array[a + i][b] != mo[i]) return false;
return true;
}
bool check_left_down(int a,int b) //左下方向
{
int i;
for (i=0;i<5;i++) if (a + i >= 6 || b - i < 0) return false;
else if (Array[a + i][b - i] != mo[i]) return false;
return true;
}
bool check_right_down(int a,int b) //右下方向
{
int i;
for (i=0;i<5;i++) if (a + i >= 6 || b + i >= 9) return false;
else if (Array[a + i][b + i] != mo[i]) return false;
return true;
}
int main()
{
int i,j;
for (i=0;i<6;i++)
for (j=0;j<9;j++)
{
if (check_right(i,j)) printf("%d %d right\n",i,j);
if (check_down(i,j)) printf("%d %d down\n",i,j);
if (check_left_down(i,j)) printf("%d %d left_down\n",i,j);
if (check_right_down(i,j)) printf("%d %d right_down\n",i,j);
// 由於模板文本具有迴文性質,故只需匹配4個方向,若對於任意模板文本,追加檢查剩餘的四個方向即可.
}
return 0;
}
若對於較為巨大的矩陣以及較多的模板文本，（例如500×500的矩陣，500個文本），如果需要在較短的時間內完成演算法（如1秒）需要使用後綴自動機，具體到這個問題就是trie圖，一種基於後綴有限狀態自動機（Suffix DFA）的專門用於處理多串匹配的數據結構，其構造方法大致是先構造模板文本的trie樹，再通過後綴鏈接生成包含所有轉移的trie圖。參考源代碼如下：
（此代碼從控制台讀入一個最大支持到1000×1000的字元矩陣，以及最多1000個文本，程序向控制台輸出每一個文本在矩陣中的起始位置和方向，以A-H表示八個方向，在Intel Pentium D 2.1G的處理器上對於任何數據均可在1s內完成運算)
#include <stdio.h>
#include <string.h>
int n,m,l,totalnode;
#define N 1100
#define M 1100000
char data[N][N];
char word[N];
typedef struct
{
int suffix,kind;
int c[26];
}trieT;
trieT trie[M];
typedef struct
{
int a,b;
char oper;
} ans_type;
ans_type ans[N];
int Q[M];
char nowoper;
const int thitah[8]={1,1,0,-1,-1,-1,0,1};
const int thital[8]={0,-1,-1,-1,0,1,1,1};
void read_data()
{
scanf("%d %d %d%*c",&n,&m,&l);
int i,j;
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++) {scanf("%c",&data[i][j]);data[i][j]-='A';}
scanf("%*c");
}
}
void insert(int s,int len)
{
int i,pnt=1;
for (i=len-1;i>=0;i--)
{
if (trie[pnt].c[word[i]]!=0) pnt=trie[pnt].c[word[i]];
else
{
totalnode++;
trie[pnt].c[word[i]]=totalnode;
pnt=totalnode;
trie[pnt].kind=-1;trie[pnt].suffix=0;
memset(trie[pnt].c,0,sizeof(trie[pnt].c));
}
}
trie[pnt].kind=s;
}
void init()
{
totalnode=1;
trie[1].kind=-1;trie[1].suffix=1;
memset(trie[1].c,0,sizeof(trie[1].c));
int i,j,len;
for (i=1;i<=l;i++)
{
scanf("%s",&word);
len=strlen(word);
for (j=0;j<len;j++) word[j]-='A';
insert(i,len);
}
}
void make_trie_graph()
{
int i,temp,tempnode,cl,op;
cl=0;op=0;
for (i=0;i<26;i++) if (trie[1].c[i]!=0)
{
temp=trie[1].c[i];
trie[temp].suffix=1;
if (trie[temp].kind==-1) trie[temp].kind=trie[1].kind;
Q[++op]=temp;
}else trie[1].c[i]=1;
while (cl<op)
{
tempnode=Q[++cl];
for (i=0;i<26;i++) if (trie[tempnode].c[i]!=0)
{
temp=trie[tempnode].c[i];
trie[temp].suffix=trie[trie[tempnode].suffix].c[i];
if (trie[temp].kind==-1) trie[temp].kind=trie[trie[temp].suffix].kind;
Q[++op]=temp;
}else trie[tempnode].c[i]=trie[trie[tempnode].suffix].c[i];
}
}
void get_ans(int s,int h,int l)
{
while (trie[s].kind!=-1)
{
ans[trie[s].kind].a=h;ans[trie[s].kind].b=l;
ans[trie[s].kind].oper=nowoper;
s=trie[s].suffix;
}
}
void check(int h,int l)
{
int pnt=1;
while ((h>0) && (h<=n) && (l>0) && (l<=m))
{
pnt=trie[pnt].c[data[h][l]];
if (trie[pnt].kind!=-1) get_ans(pnt,h,l);
h+=thitah[nowoper];l+=thital[nowoper];
}
}
void work_ans()
{
int i;
nowoper=0;for (i=1;i<=m;i++) check(1,i);
nowoper=1;for (i=1;i<=m;i++) check(1,i);for (i=2;i<=n;i++) check(i,m);
nowoper=2;for (i=1;i<=n;i++) check(i,m);
nowoper=3;for (i=1;i<=n;i++) check(i,m);for (i=1;i<m;i++) check(n,i);
nowoper=4;for (i=1;i<=m;i++) check(n,i);
nowoper=5;for (i=1;i<=m;i++) check(n,i);for (i=1;i<n;i++) check(i,1);
nowoper=6;for (i=1;i<=n;i++) check(i,1);
nowoper=7;for (i=1;i<=n;i++) check(i,1);for (i=2;i<=m;i++) check(1,i);
}
void show_ans()
{
int i;
for (i=1;i<=l;i++) printf("%d %d %c\n",ans[i].a-1,ans[i].b-1,ans[i].oper+'A');
}
int main()
{
read_data();
init();
make_trie_graph();
work_ans();
show_ans();
return 0;
}
若樓主希望學習trie圖的具體理論和構造方法，可回帖註明。
⑹ 演算法設計比賽做什麼演算法好
應該是ACM吧
就是給你8-10道演算法題目，5個小時，做出來多的題目數越多，排名越靠前，如果題目數一樣多的看用的時間。
時間的計算方法如下：
例如你A題用了20分鍾AC，然後B題有用了30分鍾AC（此時是比賽開始50分鍾），又用了30分鍾AC了C題，那麼你的時間（penalty ）是
20 + 50 + 80 = 150分鍾
比賽中常用的演算法有
1。動態規劃
2。搜索
3。貪心
4。圖論
5。組合數學
6。計算幾何
7。數論
等
推薦到
http://acm.pku.e.cn
http://acm.zju.e.cn
http://acm.h.e.cn
http://acm.timus.ru
這幾個OJ上練習
比較好的題目分類（POJ上的）
1。這個是我最喜歡的
初期:
一.基本演算法:
(1)枚舉. (poj1753,poj2965)(2008-10-27Done 位運算+寬搜)
(2)貪心(poj1328,poj2109,poj2586)
(3)遞歸和分治法.
(4)遞推.
(5)構造法.(poj3295)
(6)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖演算法:
(1)圖的深度優先遍歷和廣度優先遍歷.
(2)最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(2008-08-29Done)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓撲排序 (poj1094)(2008-09-01Done)
(5)二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)
(6)最大流的增廣路演算法(KM演算法). (poj1459,poj3436)
三.數據結構.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)
(3)簡單並查集的應用.
(4)哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼樹(poj3253)(2008-09-02Done)
(6)堆
(7)trie樹(靜態建樹、動態建樹) (poj2513)(2008-10-23Done 並查集、歐拉)
四.簡單搜索
(1)深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動態規劃
(1)背包問題. (poj1837,poj1276)
(2)型如下表的簡單DP(可參考lrj的書 page149):
1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學
(1)組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
(2)數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
(3)計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.
(1)幾何公式.
(2)叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)
(3)多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)(2008-08-29Done)
中級:
一.基本演算法:
(1)C++的標准模版庫的應用. (poj3096,poj3007)
(2)較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖演算法:
(1)差分約束系統的建立和求解. (poj1201,poj2983)(2008-09-05Done)
(2)最小費用最大流(poj2516,poj2516,poj2195)
(3)雙連通分量(poj2942)
(4)強連通分支及其縮點.(poj2186)
(5)圖的割邊和割點(poj3352)
(6)最小割模型、網路流規約(poj3308, )
三.數據結構.
(1)線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)
(2)靜態二叉檢索樹. (poj2482,poj2352)
(3)樹狀樹組(poj1195,poj3321)
(4)RMQ. (poj3264,poj3368)
(5)並查集的高級應用. (poj1703,2492)
(6)KMP演算法. (poj1961,poj2406)(2008-09-16Done)
四.搜索
(1)最優化剪枝和可行性剪枝
(2)搜索的技巧和優化 (poj3411,poj1724)
(3)記憶化搜索(poj3373,poj1691)
五.動態規劃
(1)較為復雜的動態規劃(如動態規劃解特別的施行商問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)
(3)樹型動態規劃(poj2057,poj1947,poj2486,poj3140)
六.數學
(1)組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.
(2)數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
(3)計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)隨機化演算法(poj3318,poj2454)
(5)雜題.
(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.
(1)坐標離散化.
(2)掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多邊形的內核(半平面交)(poj3130,poj3335)
(4)幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)
高級:
一.基本演算法要求:
(1)代碼快速寫成,精簡但不失風格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保證正確性和高效性. poj3434
二.圖演算法:
(1)度限制最小生成樹和第K最短路. (poj1639)
(2)最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最優比率生成樹. (poj2728)
(4)最小樹形圖(poj3164)
(5)次小生成樹.
(6)無向圖、有向圖的最小環
三.數據結構.
(1)trie圖的建立和應用. (poj2778)(2008-10-26Done 矩陣A^n)
(2)LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法
(RMQ+dfs)).(poj1330)
(3)雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的
目的). (poj2823)
(4)左偏樹(可合並堆).
(5)後綴樹(非常有用的數據結構,也是賽區考題的熱點).
(poj3415,poj3294)
四.搜索
(1)較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
(2)廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)
五.動態規劃
(1)需要用數據結構優化的動態規劃.
(poj2754,poj3378,poj3017)
(2)四邊形不等式理論.
(3)較難的狀態DP(poj3133)
六.數學
(1)組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
(2)博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.
(1)半平面求交(poj3384,poj2540)
(2)可視圖的建立(poj2966)
(3)點集最小圓覆蓋.
(4)對踵點(poj2079)
八.綜合題.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)
2。這個每個分類的題目比較多，適合作為第一個分類的擴展
說明：遞推算動歸， 離散化算數據結構， 並查集算數據結構， 博弈算動歸， 麻煩題一般都是不錯的綜合題， 最短路算圖論，數據的有序化算排序
麻煩題：1697, 1712, 1713, 1720, 1729, 1765, 1772, 1858, 1872, 1960, 1963, 2050, 2122, 2162, 2219, 2237,
簡單題目：1000, 1003, 1004, 1005, 1007, 1046, 1207, 1226, 1401, 1504, 1552, 1607, 1657, 1658, 1674, 1799, 1862, 1906, 1922, 1929, 1931, 1969, 1976, 2000, 2005, 2017, 2027, 2070, 2101, 2105, 2109, 2116, 2136, 2160, 2190, 2232, 2234, 2275, 2301, 2350, 2363, 2389, 2393, 2413, 2419, 推薦：1063, 1064, 1131, 1140, 1715, 2163,
雜題：1014, 1218, 1316, 1455, 1517, 1547, 1580, 1604, 1663, 1678, 1749, 1804, 2013, 2014, 2056, 2059, 2100, 2188, 2189, 2218, 2229, 2249, 2290, 2302, 2304, 2309, 2313, 2316, 2323, 2326, 2368, 2369, 2371, 2402, 2405, 2407, 推薦：1146, 1147, 1148, 1171, 1389, 1433, 1468, 1519, 1631, 1646, 1672, 1681, 1700, 1701, 1705, 1728, 1735, 1736, 1752, 1754, 1755, 1769, 1781, 1787, 1796, 1797, 1833, 1844, 1882, 1933, 1941, 1978, 2128, 2166, 2328, 2383, 2420,
高精度：1001, 1220, 1405, 1503,
排序：1002, 1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379, 2388, 2418, 推薦：1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380,
搜索容易：1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 1745, 1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426, 不易：1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197, 2349, 推薦：1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709, 1714, 1753, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170, 2288, 2331, 2339, 2340,
數據結構容易：1182, 1656, 2021, 2023, 2051, 2153, 2227, 2236, 2247, 2352, 2395, 不易：1145, 1177, 1195, 1227, 1661, 1834, 推薦：1330, 1338, 1451, 1470, 1634, 1689, 1693, 1703, 1724, 1988, 2004, 2010, 2119, 2274,
動態規劃容易：1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740, 1742, 1887, 1926, 1936, 1952, 1953, 1958, 1959, 1962, 1975, 1989, 2018, 2029, 2033, 2063, 2081, 2082, 2181, 2184, 2192, 2231, 2279, 2329, 2336, 2346, 2353, 2355, 2356, 2385, 2392, 2424, 不易：1019, 1037, 1080, 1112, 1141, 1170, 1192, 1239, 1655, 1695, 1707, 1733, 1737, 1837, 1850, 1920, 1934, 1937, 1964, 2039, 2138, 2151, 2161, 2178, 推薦：1015, 1635, 1636, 1671, 1682, 1692, 1704, 1717, 1722, 1726, 1732, 1770, 1821, 1853, 1949, 2019, 2127, 2176, 2228, 2287, 2342, 2374, 2378, 2384, 2411,
字元串：1488, 1598, 1686, 1706, 1747, 1748, 1750, 1760, 1782, 1790, 1866, 1888, 1896, 1951, 2003, 2121, 2141, 2145, 2159, 2337, 2359, 2372, 2406, 2408,
貪心：1042, 1065, 1230, 1323, 1477, 1716, 1784,
圖論容易：1161, 1164, 1258, 1175, 1308, 1364, 1776, 1789, 1861, 1939, 1940, 1943, 2075, 2139, 2387, 2394, 2421, 不易：1041, 1062, 1158, 1172, 1201, 1275, 1718, 1734, 1751, 1904, 1932, 2173, 2175, 2296, 網路流：1087, 1273, 1698, 1815, 2195, 匹配：1274, 1422, 1469, 1719, 2060, 2239, Euler：1237, 1637, 1394, 2230, 推薦：2049, 2186,
計算幾何容易：1319, 1654, 1673, 1675, 1836, 2074, 2137, 2318, 不易：1685, 1687, 1696, 1873, 1901, 2172, 2333, 凸包：1113, 1228, 1794, 2007, 2187,
模擬容易：1006, 1008, 1013, 1016, 1017, 1169, 1298, 1326, 1350, 1363, 1676, 1786, 1791, 1835, 1970, 2317, 2325, 2390, 不易：1012, 1082, 1099, 1114, 1642, 1677, 1684, 1886,
數學容易：1061, 1091, 1142, 1289, 1305, 1306, 1320, 1565, 1665, 1666, 1730, 1894, 1914, 2006, 2042, 2142, 2158, 2174, 2262, 2305, 2321, 2348, 不易：1067, 1183, 1430, 1759, 1868, 1942, 2167, 2171, 2327, 推薦：1423, 1450, 1640, 1702, 1710, 1721, 1761, 1830, 1930, 2140,
⑺ 字元串匹配演算法的使用（未完待整理）
字元串的匹配在Java中都知道使用indexOf函數來實現，那麼其匹配演算法是怎麼樣的呢？
單模式和多模式的區別就是一次遍歷主串能否將多個模式的字元串都查找出來。
英文全稱為Brute Force，暴力匹配演算法，匹配字元串的方法比較暴力，也比較簡單易懂。其大概的思路就是：
我們可以看到，在極端情況下，在主串 aaaa...aab 中尋找模式串 aab ，那麼總共需要尋找(n-m+1)次，且每次都需要比對m次，那麼時間復雜度將是 (n-m+1)*m ，即 O(n*m) ；但實際上並不會這么低效，因為我們的使用場景中主串和模式串都不會太長，而且在每個子串和模式串進行比對時，只要中途有一個不匹配，那麼當前比對就會提前結束，因此大部分情況下，時間復雜度都會比 O(n*m) 要好。
我們在BF演算法的基礎上引入哈希演算法，我們不需要將每個子串與模式串逐個字元地進行比較，而是計算得出每個子串的hash值，然後和模式串的hash值進行比較，如果有相等的，那就說明有子串和模式串匹配上了。
雖然我們只需要比對模式串和子串的hash值就能得到匹配結果，次數為(n-m+1)，但是對每個子串進行hash計算的時候，是要遍歷每個字元的，因此次數也是m，那麼總的時間復雜度還是 O(n*m) ，並沒有明顯地提升。
那麼我們該如何想出一個辦法，使得每個子串hash值的計算時間得到提升呢？這就是RK演算法的精髓，假設子串包含的字元集中元素個數為k，那麼就用k進制數來代表這個子串，然後hash的過程就是將這個k進制的數轉換為十進制的數，這個十進制的數就是該子串的hash值。
相鄰子串的hash值計算是有規律的，我們只需要遍歷一次主串就能得到所有子串的hash值，演算法復雜度為O(n)，而不是像原先一樣，每個子串都需要O(m)的時間復雜度。
然後將模式串的hash值和所有子串的hash值進行比較，每次比較的時間復雜度是 O(1) ，總共比較(n-m+1)次，所以RK演算法的總的時間開銷為 O(n)+O(1)*O(n-m+1) ，即為 O(n) ，時間復雜度比BF演算法更加高效。
當然，有hash的地方就有可能會存在hash沖突，有可能子串和hash值和模式串的hash值是一樣的，但內容就是不一樣，此時怎麼辦呢？其實很簡單，對於hash值一樣的子串，我們增加雙保險，再比較一下這m個字元是否都一樣即可，總的時間開銷為 O(n)+O(1)*O(n-m+1)+O(m) ，即為 O(n) 。
如果極端情況下出現了很多hash沖突呢？我們對於每個和模式串相同hash值的子串都需要逐一再進行比較，那麼總的時間開銷就會為 O(n)+O(1)*O(n-m+1)+O(m)*O(n-m+1) ，即為 O(n*m) ，不過這種概率太小了，大部分情況下都不會這樣。
在真正的文本編輯器中查找和替換某個字元串時，使用的演算法既不是上述的BF演算法，也不是RK演算法；BF演算法只適合不是很長的主串，RK演算法則要設計一個沖突概率很低的hash演算法，這個比較困難，所以實際使用的是BM演算法，它是工程中非常常用的一種字元串匹配演算法，效率也是最高的。
演算法的思想和過程有些復雜，待以後整理。
KMP演算法在本質上是和BM演算法一樣的。演算法的思想和過程有些復雜，待以後整理。
瀏覽器輸入框中的智能輸入匹配是怎麼實現的，它是怎麼做動態字元串匹配查找的呢？這就用到了Trie樹。
又名字典樹，是一種專門用來快速查找字元串前綴匹配結果的樹形結構，其本質就是將所有字元串的重復的前綴合並在一起，構造一個多叉樹。
其中，根節點不包含任何信息，每個節點表示一個字元，從根節點到紅色節點的一條路徑表示存儲的一個字元串。當我們在如上Trie樹中查找"he"時，發現"he"並非是一個字元串，而是"hello"和"her"的公共前綴，那麼就會找到這兩個字元串返回。
Trie樹在內存中是如何存儲的呢？因為每一個節點都可能是包含所有字元的，所以每一個節點都是一個數組（或者散列表），用來存儲每個字元及其後綴節點的指針。
使用Trie樹，最開始構建的時候，時間復雜度為 O(n) ，其中n為所有字元串長度之和，但是一旦構建完成，頻繁地查詢某個字元串是非常高效的，時間復雜度為 O(k) ，其中k為查找字元串的長度。
Trie樹雖然查詢效率很高，但是比較浪費內存，每一個節點都必須維護一個數組存放所有可能的字元數據及其指向下一個節點的指針，因此在所有字元串公共前綴並不多的時候，內存空間浪費地就更多了。這種問題其實也有對應的解決辦法，我們可以不使用數組，而是使用有序數組、散列表、紅黑樹來存放，可以相應地降低性能來節省內存空間。
Trie樹除了可以實現瀏覽器動態輸入內容查找候選項的功能外，還可以實現多模式地敏感詞匹配功能。假設我們需要對用戶輸入的內容進行敏感詞檢查，將所有的敏感內容用***代替，那麼該如何實現呢？
首先我們可以維護一個敏感詞字典，使用上述四種單模式匹配演算法也可以實現，但是需要遍歷N次用戶輸入的內容，其中N是所有敏感詞的模式串，顯得非常低效。但是我們如果將敏感詞字典維護為一個Trie樹，然後將用戶輸入的內容從位置0開始在Trie樹中進行查詢，如果匹配到紅色節點，那麼說明有敏感詞；如果沒有匹配到紅色節點，就從用戶輸入內容的下一個位置開始繼續在Trie樹中查詢，直至將用戶輸入內容遍歷完，因此我們只是遍歷了一遍主串。
然而更高效的多模式字元串匹配使用地更多的是如下的AC自動機。
如果把Trie樹比作BF演算法，KMP演算法是BF演算法的改進，那麼AC自動機就是利用同樣的思想改進了Trie樹。
演算法的思想和過程有些復雜，待以後整理。
⑻ 是的 計算機演算法
計算機演算法是以一步接一步的方式來詳細描述計算機如何將輸入轉化為所要求的輸出的過程，或者說，演算法是對計算機上執行的計算過程的具體描述。
編輯本段演算法性質一個演算法必須具備以下性質： （1）演算法首先必須是正確的，即對於任意的一組輸入，包括合理的輸入與不合理的輸入，總能得到預期的輸出。如果一個演算法只是對合理的輸入才能得到預期的輸出，而在異常情況下卻無法預料輸出的結果，那麼它就不是正確的。 （2）演算法必須是由一系列具體步驟組成的，並且每一步都能夠被計算機所理解和執行，而不是抽象和模糊的概念。 （3）每個步驟都有確定的執行順序，即上一步在哪裡，下一步是什麼，都必須明確，無二義性。 （4）無論演算法有多麼復雜，都必須在有限步之後結束並終止運行，即演算法的步驟必須是有限的。在任何情況下，演算法都不能陷入無限循環中。 一個問題的解決方案可以有多種表達方式，但只有滿足以上4個條件的解才能稱之為演算法。編輯本段重要演算法A*搜尋演算法
俗稱A星演算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的NPC的移動計算，或線上游戲的BOT的移動計算上。該演算法像Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。
Beam Search
束搜索(beam search)方法是解決優化問題的一種啟發式方法，它是在分枝定界方法基礎上發展起來的，它使用啟發式方法估計k個最好的路徑，僅從這k個路徑出發向下搜索，即每一層只有滿意的結點會被保留，其它的結點則被永久拋棄，從而比分枝定界法能大大節省運行時間。束搜索於20 世紀70年代中期首先被應用於人工智慧領域,1976 年Lowerre在其稱為HARPY的語音識別系統中第一次使用了束搜索方法，他的目標是並行地搜索幾個潛在的最優決策路徑以減少回溯，並快速地獲得一個解。
二分取中查找演算法
一種在有序數組中查找某一特定元素的搜索演算法。搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。這種搜索演算法每一次比較都使搜索范圍縮小一半。
Branch and bound
分支定界(branch and bound)演算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯演算法不同，分支定界演算法採用廣度優先或最小耗費優先的方法搜索解空間樹，並且，在分支定界演算法中，每一個活結點只有一次機會成為擴展結點。
數據壓縮
數據壓縮是通過減少計算機中所存儲數據或者通信傳播中數據的冗餘度，達到增大數據密度，最終使數據的存儲空間減少的技術。數據壓縮在文件存儲和分布式系統領域有著十分廣泛的應用。數據壓縮也代表著尺寸媒介容量的增大和網路帶寬的擴展。
Diffie–Hellman密鑰協商
Diffie–Hellman key exchange，簡稱「D–H」，是一種安全協議。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在後續的通訊中作為對稱密鑰來加密通訊內容。
Dijkstra』s 演算法
迪科斯徹演算法（Dijkstra）是由荷蘭計算機科學家艾茲格·迪科斯徹（Edsger Wybe Dijkstra）發明的。演算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，迪科斯徹演算法可以用來找到兩個城市之間的最短路徑。
動態規劃
動態規劃是一種在數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種演算法的基礎，被廣泛應用於計算機科學和工程領域。比較著名的應用實例有：求解最短路徑問題，背包問題，項目管理，網路流優化等。這里也有一篇文章說得比較詳細。
歐幾里得演算法
在數學中，輾轉相除法，又稱歐幾里得演算法，是求最大公約數的演算法。輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。
最大期望（EM）演算法
在統計計算中，最大期望（EM）演算法是在概率（probabilistic）模型中尋找參數最大似然估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variable）。最大期望經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。最大期望演算法經過兩個步驟交替進行計算，第一步是計算期望（E），利用對隱藏變數的現有估計值，計算其最大似然估計值；第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。M 步上找到的參數估計值被用於下一個 E 步計算中，這個過程不斷交替進行。
快速傅里葉變換(FFT)
快速傅里葉變換（Fast Fourier Transform，FFT），是離散傅里葉變換的快速演算法，也可用於計算離散傅里葉變換的逆變換。快速傅里葉變換有廣泛的應用，如數字信號處理、計算大整數乘法、求解偏微分方程等等。
哈希函數
HashFunction是一種從任何一種數據中創建小的數字「指紋」的方法。該函數將數據打亂混合，重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字元串。好的散列函數在輸入域中很少出現散列沖突。在散列表和數據處理中，不抑制沖突來區別數據，會使得資料庫記錄更難找到。
堆排序
Heapsort是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法。堆積樹是一個近似完全二叉樹的結構，並同時滿足堆積屬性：即子結點的鍵值或索引總是小於（或者大於）它的父結點。
歸並排序
Merge sort是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
RANSAC 演算法
RANSAC 是」RANdom SAmpleConsensus」的縮寫。該演算法是用於從一組觀測數據中估計數學模型參數的迭代方法，由Fischler and Bolles在1981提出，它是一種非確定性演算法，因為它只能以一定的概率得到合理的結果，隨著迭代次數的增加，這種概率是增加的。該演算法的基本假設是觀測數據集中存在」inliers」（那些對模型參數估計起到支持作用的點）和」outliers」（不符合模型的點），並且這組觀測數據受到雜訊影響。RANSAC 假設給定一組」inliers」數據就能夠得到最優的符合這組點的模型。
RSA加密演演算法
這是一個公鑰加密演算法，也是世界上第一個適合用來做簽名的演算法。今天的RSA已經專利失效，其被廣泛地用於電子商務加密，大家都相信，只要密鑰足夠長，這個演算法就會是安全的。
並查集Union-find
並查集是一種樹型的數據結構，用於處理一些不相交集合（Disjoint Sets）的合並及查詢問題。常常在使用中以森林來表示。
Viterbi algorithm
尋找最可能的隱藏狀態序列(Finding most probable sequence of hidden states)。編輯本段演算法特點1.有窮性。一個演算法應包含有限的操作步驟，而不能是無限的。事實上「有窮性」往往指「在合理的范圍之內」。如果讓計算機執行一個歷時1000年才結束的演算法，這雖然是有窮的，但超過了合理的限度，人們不把他是為有效演算法。 2. 確定性。演算法中的每一個步驟都應當是確定的，而不應當是含糊的、模稜兩可的。演算法中的每一個步驟應當不致被解釋成不同的含義，而應是十分明確的。也就是說，演算法的含義應當是唯一的，而不應當產生「歧義性」。 3. 有零個或多個輸入、所謂輸入是指在執行演算法是需要從外界取得必要的信息。 4. 有一個或多個輸出。演算法的目的是為了求解，沒有輸出的演算法是沒有意義的。 5.有效性。 演算法中的每一個 步驟都應當能有效的執行。並得到確定的結果。編輯本段演算法與程序雖然演算法與計算機程序密切相關，但二者也存在區別：計算機程序是演算法的一個實例，是將演算法通過某種計算機語言表達出來的具體形式；同一個演算法可以用任何一種計算機語言來表達。 演算法列表 圖論 路徑問題 0/1邊權最短路徑 BFS 非負邊權最短路徑（Dijkstra） 可以用Dijkstra解決問題的特徵 負邊權最短路徑 Bellman-Ford Bellman-Ford的Yen-氏優化 差分約束系統 Floyd 廣義路徑問題 傳遞閉包 極小極大距離 / 極大極小距離 Euler Path / Tour 圈套圈演算法 混合圖的 Euler Path / Tour Hamilton Path / Tour 特殊圖的Hamilton Path / Tour 構造 生成樹問題 最小生成樹 第k小生成樹 最優比率生成樹 0/1分數規劃 度限制生成樹 連通性問題 強大的DFS演算法 無向圖連通性 割點 割邊 二連通分支 有向圖連通性 強連通分支 2-SAT 最小點基 有向無環圖 拓撲排序 有向無環圖與動態規劃的關系 二分圖匹配問題 一般圖問題與二分圖問題的轉換思路 最大匹配 有向圖的最小路徑覆蓋 0 / 1矩陣的最小覆蓋 完備匹配 最優匹配 穩定婚姻 網路流問題 網路流模型的簡單特徵和與線性規劃的關系 最大流最小割定理 最大流問題 有上下界的最大流問題 循環流 最小費用最大流 / 最大費用最大流 弦圖的性質和判定 組合數學 解決組合數學問題時常用的思想 逼近 遞推 / 動態規劃 概率問題 Polya定理 計算幾何 / 解析幾何 計算幾何的核心：叉積 / 面積 解析幾何的主力：復數 基本形 點 直線，線段 多邊形 凸多邊形 / 凸包 凸包演算法的引進，卷包裹法 Graham掃描法 水平序的引進，共線凸包的補丁 完美凸包演算法 相關判定 兩直線相交 兩線段相交 點在任意多邊形內的判定 點在凸多邊形內的判定 經典問題 最小外接圓 近似O(n)的最小外接圓演算法 點集直徑 旋轉卡殼，對踵點 多邊形的三角剖分 數學 / 數論 最大公約數 Euclid演算法 擴展的Euclid演算法 同餘方程 / 二元一次不定方程 同餘方程組 線性方程組 高斯消元法 解mod 2域上的線性方程組 整系數方程組的精確解法 矩陣 行列式的計算 利用矩陣乘法快速計算遞推關系 分數 分數樹 連分數逼近 數論計算 求N的約數個數 求phi(N) 求約數和 快速數論變換 …… 素數問題 概率判素演算法 概率因子分解 數據結構 組織結構 二叉堆 左偏樹 二項樹 勝者樹 跳躍表 樣式圖標 斜堆 reap 統計結構 樹狀數組 虛二叉樹 線段樹 矩形面積並 圓形面積並 關系結構 Hash表 並查集 路徑壓縮思想的應用 STL中的數據結構 vector deque set / map 動態規劃 / 記憶化搜索 動態規劃和記憶化搜索在思考方式上的區別 最長子序列系列問題 最長不下降子序列 最長公共子序列 一類NP問題的動態規劃解法 樹型動態規劃 背包問題 動態規劃的優化 四邊形不等式 函數的凸凹性 狀態設計 規劃方向 線性規劃 常用思想 二分 最小表示法 串 KMP Trie結構 後綴樹/後綴數組 LCA/RMQ 有限狀態自動機理論 排序 選擇/冒泡 快速排序 堆排序 歸並排序 基數排序 拓撲排序 排序網路
擴展閱讀：
1
《計算機演算法設計與分析導論》朱清新等編著人民郵電出版社
開放分類：
計算機，演算法