李萍　趙潤林

摘要：模式匹配是字符串的基本運算之一，也是數(shù)據(jù)結(jié)構(gòu)課程的重點算法之一。在當(dāng)今文本信息海量增長的時代，如何快速地定位就顯得尤為重要。該文通過樸素模式匹配算法與KMP算法的比較說明各自的優(yōu)缺點，同時通過提高獲取next數(shù)組的效率，加快KMP算法的匹配速率。

關(guān)鍵詞：模式匹配；KMP；NEXT函數(shù)；文本搜索

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2017）18-0025-02

從計算機誕生至今，文本信息海量地增長，無論是在金融、航海、DNA檢測、網(wǎng)絡(luò)入侵等領(lǐng)域都需要在文本中快速地查找所需要的信息，因此設(shè)計出一個好模式匹配算法，不公可以高效地進(jìn)行定位，還可以提高文本編輯能力，提高改善人類的生活。

模式匹配即子串的定位操作，是數(shù)據(jù)結(jié)構(gòu)中邏輯結(jié)構(gòu)為串的最重要操作之一。該算法的主要目的是找出特定的模式串在一個較長的字符串中出現(xiàn)的位置。如有兩個字符串T稱為模式串，字符串s稱為主串，找出模式T在主S中的首次出現(xiàn)的位置。一旦模式T在目標(biāo)s中找到，就稱發(fā)生一次匹配。例如，目標(biāo)串S=ababeabcaebab，模式串T=abcac，則匹配結(jié)果為6，其中經(jīng)典的模式匹配算法包括樸素匹配算法、KMP。

1樸素模式匹配算法

樸素模式匹配算法的基本思想是在模式串T和主串S中，使用循環(huán)變量I，j，分別在模式串和主串中循環(huán)跑動，如果模式串與主串對應(yīng)字符相等S[i]=T[j]，則同時后移；如果模式串與主串對應(yīng)字符不相等S[i]≠[j]，則模式串回滾到起始位置，而主串回滾到起始位置的下一個字符。如此一直循環(huán)直至主串結(jié)束或模式串結(jié)束。樸素模式匹配算法的回溯演示如下：

算法流程圖描述如下：

2 KMP算法

與樸素模式匹配算法比較，KMP算法最大的特點是模式串在匹配不相等的情況下，不再回溯，而是匹配串進(jìn)行滑動，所以匹配串滑動的位置是算法的關(guān)鍵。由于模式串已匹配的字符串與主串已匹配內(nèi)容相同，從模式串部分匹配字符中從前和從后數(shù)的字符串如果相同，即相同字符串無需再進(jìn)行匹配，即模式串滑動的位置為相同字符數(shù)加1?；瑒友菔救缦拢?/p>

4總結(jié)

本文通過分析樸素匹配算法與KMP算法如何進(jìn)行字符串比較，在比較相等與不相等時模式串與主串如何移動，說明兩者的優(yōu)缺點，并且在KMP算法中通過改進(jìn)next函數(shù)值的計算，提高KMP匹配效率，并通過上機驗證實現(xiàn)算法。endprint