任憲臻 任美玲

(1.北京信息職業(yè)技術(shù)學(xué)院 軟件與信息學(xué)院，北京 100018;2.煙臺(tái)南山學(xué)院 工學(xué)院計(jì)算機(jī)系，山東 煙臺(tái) 265700)

字符串是以字符作為數(shù)據(jù)元素的線(xiàn)性表，是非常重要的非數(shù)值處理對(duì)象。目前大量地處理非數(shù)值計(jì)算問(wèn)題都給通過(guò)計(jì)算機(jī)來(lái)實(shí)現(xiàn)，例如，文字編輯、信息檢索、詞法掃描、符號(hào)處理、自然語(yǔ)言翻譯等。在事務(wù)處理程序中，如客戶(hù)信息、貨物產(chǎn)地等一般也都是作為字符串處理，因此字符串在很多領(lǐng)域都得到了廣泛應(yīng)用。字符串的邏輯結(jié)構(gòu)與線(xiàn)性表的邏輯結(jié)構(gòu)相同，但是它的基本操作卻和線(xiàn)性表的基本操作有著很大的差別。線(xiàn)性表的基本操作主要是以“單個(gè)數(shù)據(jù)元素”作為操作對(duì)象，比如在線(xiàn)性表中的某個(gè)位置插入或刪除一個(gè)元素、在線(xiàn)性表中按位查找或者按值查找某個(gè)元素等；而字符串的基本操作的操作對(duì)象卻通常是一個(gè)“字符串整體”，比如在字符串的某個(gè)位置插入或者刪除一個(gè)子串、在字符串中定位查找某個(gè)子串等。

字符串被廣泛應(yīng)用在非數(shù)值處理領(lǐng)域，其中字符串的查找定位操作是最經(jīng)常用到的。字符串的查找定位也經(jīng)常被稱(chēng)為字符串的模式匹配，是指在主串中尋找子串的一個(gè)過(guò)程。例如，如果給定兩個(gè)字符串：S=“s1s2…sn”，T=“t1t2…tm”（1 ≤m ≤n），在主串S 中尋找子串T 的過(guò)程就稱(chēng)為模式匹配，其中字符串T 稱(chēng)為模式。如果在主串S 中找到了一個(gè)和模式T 相同的字符子串，則表示在主串S 中查找模式T 成功，也稱(chēng)模式T 匹配成功。當(dāng)模式T 匹配成功時(shí)，返回模式T 的首字符在主串S 中的位置（本文設(shè)定字符的位置序號(hào)從1 開(kāi)始計(jì)數(shù)）；如果在主串S 中找不到與模式T 相同的子串，則表示在主串S 中查找模式T 失敗，即模式T 匹配失敗。當(dāng)模式T 匹配失敗時(shí)，返回?cái)?shù)值0。

字符串的模式匹配操作被頻繁應(yīng)用在郵件過(guò)濾、搜索引擎、文本處理以及數(shù)據(jù)庫(kù)系統(tǒng)中。在模式匹配的過(guò)程中，問(wèn)題的規(guī)模通常會(huì)很大，所以常常需要在大量信息中執(zhí)行匹配操作，因此模式匹配算法的一次執(zhí)行時(shí)間是不容忽視的。此外，因?yàn)槟Ｊ狡ヅ洳僮鹘?jīng)常被調(diào)用，所以匹配操作的執(zhí)行頻率非常高，因此模式匹配算法改進(jìn)所取得的效益累積效應(yīng)往往比表面上看起來(lái)要大的多。在字符串的模式匹配算法中，有兩種主要的模式匹配算法：Brute-Force 算法（簡(jiǎn)稱(chēng)BF 算法）和KMP 算法，本文主要論述BF 算法。

BF 算法是一種非常簡(jiǎn)單而又直觀(guān)的模式匹配算法，“蠻力匹配”是BF 算法的基本思想：從主串S 的第一個(gè)字符開(kāi)始和模式T 的第一個(gè)字符開(kāi)始進(jìn)行比較，若比較相等，則繼續(xù)比較主串S 和模式T 的后續(xù)字符；否則，從主串S 的第二個(gè)字符開(kāi)始和模式T 的第一個(gè)字符重新進(jìn)行比較……重復(fù)上述過(guò)程，直至字符串S 或模式T 中所有字符均被比較完畢。若BF 算法的模式匹配過(guò)程結(jié)束時(shí)，模式T 中的字符全部被比較完畢，則表示模式T 匹配成功，返回本趟匹配的開(kāi)始位置，即模式T 的首字符在主串S 中的序號(hào)；否則模式T 匹配失敗，返回?cái)?shù)值0。

模式匹配BF 算法的偽代碼描述如下所示：

算法：BF

輸入：主串S，模式T

輸出：T 在S 中的位置序號(hào)(從1 開(kāi)始計(jì)數(shù))

1.設(shè)定S 和T 比較的開(kāi)始下標(biāo) i=0，j=0（從0 開(kāi)始）；

2.重復(fù)2.1 和2.2 兩步操作，直到S 或T 的所有字符均被比較完畢：

2.1 如果S[i]==T[j]，則繼續(xù)比較S 和T 的下一對(duì)字符；

2.2 否則(即S[i]!=T[j])，則將S和T比較的下標(biāo)i和j進(jìn)行回溯，準(zhǔn)備下一趟比較；

3.如果T中所有字符均比較完，則匹配成功，返回本趟匹配的起始位置；否則返回 0；

我們通過(guò)主串S=“ababcabcacbab”，模式T=”abcac”來(lái)看一下BF 算法匹配過(guò)程，串S 和串T 的表示如圖1 所示：

第一趟匹配：開(kāi)始下標(biāo)i=0，j=0，當(dāng)i=2，j=2 時(shí)匹配失敗，這時(shí)i回溯到 1，j 回溯到 0；

第二趟匹配：開(kāi)始下標(biāo)i=1，j=0，當(dāng)i=1，j=0 時(shí)匹配失敗，這時(shí)i回溯到 2，j 回溯到 0；

第三趟匹配：開(kāi)始下標(biāo)i=2，j=0，當(dāng)i=6，j=4 時(shí)匹配失敗，這時(shí)i回溯到 3，j 回溯到0；

第四趟匹配：開(kāi)始下標(biāo)i=3，j=0，當(dāng)i=3，j=0 時(shí)匹配失敗，這時(shí)i 回溯到 4，j回溯到0；

第五趟匹配：開(kāi)始下標(biāo)i=4，j=0，當(dāng)i=4，j=0 時(shí)匹配失敗，這時(shí)i回溯到 5，j回溯到 0；

第六趟匹配：開(kāi)始下標(biāo)i=5，j=0，當(dāng)i=10，j=5時(shí)，模式T中的全部字符都被比較完畢，所以模式匹配成功，此時(shí)應(yīng)該返回模式T 在主串S 中的位置序號(hào)6。

通過(guò)以上分析，用java 程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)的BF 算法及對(duì)算法進(jìn)行的測(cè)試如圖2、圖3、圖4 所示：

從以上BF 算法的分析與實(shí)現(xiàn)我們可以發(fā)現(xiàn)，BF 算法簡(jiǎn)單，但是其實(shí)效率比較低。通過(guò)分析BF 算法的執(zhí)行過(guò)程，我們可以得知造成BF 算法效率比較低的最重要的原因就是每趟匹配失敗后的下標(biāo)回溯，即在某趟匹配失敗后，對(duì)于主串S 要回溯到本趟匹配開(kāi)始字符的下一個(gè)字符，而模式T要回溯到第一個(gè)字符，而在有些情況下，這些回溯往往是不必要的。由 Knuth、Morris 和Pratt 三位科學(xué)家共同提出并設(shè)計(jì)的KMP 算法對(duì)BF 算法做了很大的改進(jìn)，它主要消除了匹配不成功的情況下主串指針不必要的回溯，從而使模式匹配算法的效率在某種程度上有了很大的提高。