KMP算法實現(xiàn)代碼
2018-07-20 來源：open-open
在文章里只給出了算法代碼以及解釋，后邊的留下了一份中文一份英文的參考博文地址以便深刻理解KMP算法。ps：中文的親測，解釋原理簡單易懂。
KMP算法
算法思想
相比蠻力算法，KMP算法預(yù)先計算出了一個哈希表，用來指導(dǎo)在匹配過程中匹配失敗后嘗試下次匹配的起始位置，以此避免重復(fù)的讀入和匹配過程。這個哈希表被叫做“部分匹配值表(**Particial match table**)”，它的設(shè)計是算法精妙之處。部分匹配值表
要理解部分匹配值表，就得先了解字符串的前綴(prefix)和后綴(postfix)。
前綴:除字符串最后一個字符以外的所有頭部串的組合。
后綴：除字符串第一個字符以外的所有尾部串的組合。
部分匹配值：一個字符串的前綴和后綴中最長共有元素的長度。
舉例說明：字符串ABCAB
前綴：{A， AB， ABC， ABCA}
后綴：{BCAB， CAB， AB， B}
部分匹配值：2 （AB）
而所謂的部分匹配值表，則為模式串的所有前綴以及其本身的部分匹配值。
前綴:除字符串最后一個字符以外的所有頭部串的組合。
后綴：除字符串第一個字符以外的所有尾部串的組合。
部分匹配值：一個字符串的前綴和后綴中最長共有元素的長度。
舉例說明：字符串ABCAB
前綴：{A， AB， ABC， ABCA}
后綴：{BCAB， CAB， AB， B}
部分匹配值：2 （AB）
而所謂的部分匹配值表，則為模式串的所有前綴以及其本身的部分匹配值。
標(biāo)簽： 代碼
版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。
上一篇:c#xml文檔操作類(2)
下一篇:DOM4J生成、解析XML實例
最新資訊
熱門推薦