字符串相關(guān)算法

1、字符串相關(guān)算法 主講：李躍主要內(nèi)容nKMP算法n字符串HASHn最小表示法nTRIE樹nAC自動(dòng)機(jī)n有限狀態(tài)自動(dòng)機(jī)DFAn后綴數(shù)組什么是串n由字母、符號(hào)組成的線性表n與串有關(guān)的問題及算法在實(shí)際應(yīng)用中非常廣泛n例如 文本搜索與串有關(guān)的概念n長(zhǎng)度n字符集n前綴n后綴n字典序模式匹配n主串（text）n模版串（pattern）n樸素算法nKMP算法nMaxtrix67 blog KMP算法詳解nhttp:/ -1 意義：任何串的第一個(gè)字符的模式值規(guī)定為-1。 (2)nextj=k 意義：模式串T中下標(biāo)為j的字符，如果j的前面k個(gè)字符與開頭的k個(gè)字符相等,且Tj != Tk （1kj）。即T0T1T2

2、。Tk-1=Tj-kTj-k+1Tj-k+2Tj-1 且Tj != Tk.（1kj）;KMP重點(diǎn)：next函數(shù)的意義n nexti=k 表示i的前有k個(gè)字符與0-(k-1)相同，如n s = “ a b c a b c a b c 0”n next= -1 0 0 0 1 2 3 4 5 6 例題n字串尋址n54/JudgeOnline/showproblem?problem_id=1139Hash是什么？n將某個(gè)對(duì)象對(duì)應(yīng)到一個(gè)關(guān)鍵值，然后通過(guò)關(guān)鍵值歸類，放入到一個(gè)表中（哈希表），今后可以根據(jù)關(guān)鍵值迅速查找nHash可以用來(lái)判重和統(tǒng)計(jì)數(shù)目字符串HashnHa

3、sh中最常用的是字符串Hashn將一個(gè)字符串對(duì)應(yīng)到一個(gè)整型數(shù)值，插入到哈希表n對(duì)應(yīng)方法有很多種，甚至可以根據(jù)問題的特殊性自己構(gòu)造，常用的有Rabin-Karp，ELFHashRabin-Karpn如果字符串中可能出現(xiàn)的字符有k個(gè)，則可以將字符串對(duì)應(yīng)到k進(jìn)制數(shù)n例如，如果字符串只可能為小寫字母組成，則acm就對(duì)應(yīng)到0262+2*26+12nlog(263)/log(26)=13.40300137386187867719n當(dāng)字符串長(zhǎng)度不超過(guò)13的時(shí)候，用long long作關(guān)鍵值類型，加上字符串長(zhǎng)度作為限制，每個(gè)字符串唯一對(duì)應(yīng)關(guān)鍵值n當(dāng)字符串長(zhǎng)度超過(guò)13的時(shí)候，就要進(jìn)一步驗(yàn)證LEFhash算法nE

4、LFhash: 黑書 P96 1.4.3nint ELFhash(char *key) n n unsigned long h=0; n while(*key) n n h=(h24; n h&=g; n n return h%MOD; n Hash沖突的處理n不同的字符串可能映射到同一個(gè)key值。n（1） 開放地址法。n（2）拉鏈法。最小表示法n2003年 冬令營(yíng) 周源 論文TRIE樹n又稱字典樹n可用于字典中單詞的查找n優(yōu)點(diǎn)：節(jié)省查找時(shí)間n缺點(diǎn)：字符集太大時(shí) 空間耗費(fèi)大AC自動(dòng)機(jī)n多模式匹配nAC自動(dòng)機(jī)=Trie樹+KMPnAC自動(dòng)機(jī)算法詳解 http:/ 以及一個(gè)文本 要求找出每個(gè)單詞出現(xiàn)的次數(shù)及位置n計(jì)數(shù)問題n實(shí)現(xiàn)：n1.構(gòu)建TRIE樹n2.通過(guò)一次BFS連后向邊n例題：hdu 2222nhttp:/ 許智磊：后綴數(shù)組n后綴：n后綴數(shù)組SA：nRank數(shù)組nHeight數(shù)組：n例題： POJ 2774練習(xí)nPOJ上的字符串題目：nkmp 2752 2406 1961 2185nHash & tire樹 1