字符串匹配算法的改進手冊一、字符串匹配算法概述

字符串匹配算法是計算機科學(xué)中常用的算法之一，主要用于在一個較長的文本串（文本）中查找一個較短的模式串（模式）是否存在及其位置。根據(jù)不同的應(yīng)用場景和性能需求，有多種字符串匹配算法被提出，如暴力匹配、KMP算法、Boyer-Moore算法等。本手冊旨在介紹幾種常見的字符串匹配算法，并探討其改進方法。

二、常見字符串匹配算法

（一）暴力匹配算法

1.原理：暴力匹配算法是最簡單的字符串匹配方法，通過逐個字符比較模式串和文本串，若不匹配則模式串向右移動一個字符，直到找到匹配或遍歷完文本。

2.步驟：

(1)從文本串的第一個字符開始，與模式串的第一個字符比較。

(2)若所有字符匹配，返回匹配位置；若不匹配，模式串向右移動一位，重新比較。

(3)重復(fù)步驟(2)，直到匹配成功或文本串遍歷完畢。

3.時間復(fù)雜度：最壞情況下為O(nm)，其中n是文本串長度，m是模式串長度。

（二）KMP算法

1.原理：KMP算法通過預(yù)處理模式串，構(gòu)建部分匹配表（Next數(shù)組），避免暴力匹配中的無效回溯。

2.步驟：

(1)構(gòu)建Next數(shù)組：計算模式串中每個前綴的最長相同前后綴長度。

(2)匹配過程：

a.從文本串和模式串的第一個字符開始比較。

b.若匹配，指針均向右移動一位；若不匹配，利用Next數(shù)組確定模式串的移動位置。

c.重復(fù)步驟b，直到匹配成功或文本串遍歷完畢。

3.時間復(fù)雜度：O(n+m)，顯著優(yōu)于暴力匹配。

（三）Boyer-Moore算法

1.原理：Boyer-Moore算法通過好后綴規(guī)則和壞字符規(guī)則，從文本串的末尾開始匹配，減少比較次數(shù)。

2.步驟：

(1)構(gòu)建壞字符表和好后綴表：

a.壞字符表記錄模式串中每個字符在模式串中最右側(cè)的位置。

b.好后綴表記錄模式串中每個后綴的最長相同前綴長度。

(2)匹配過程：

a.從文本串的末尾開始，與模式串的末尾字符比較。

b.若匹配，指針均向左移動一位；若不匹配，根據(jù)壞字符規(guī)則或好后綴規(guī)則移動模式串位置。

c.重復(fù)步驟b，直到匹配成功或文本串遍歷完畢。

3.時間復(fù)雜度：最佳情況下為O(n/m)，但最壞情況下仍為O(nm)。

三、字符串匹配算法的改進方法

（一）優(yōu)化暴力匹配算法

1.提前終止：若文本串中包含多個模式串實例，可提前終止搜索以節(jié)省時間。

2.字符預(yù)處理：對文本串和模式串進行編碼或哈希，減少比較開銷。

（二）KMP算法的改進

1.改進Next數(shù)組：使用更高效的方法構(gòu)建Next數(shù)組，如利用動態(tài)規(guī)劃。

2.并行匹配：在多核環(huán)境下，可將文本串分塊并行處理，加速匹配過程。

（三）Boyer-Moore算法的改進

1.動態(tài)更新規(guī)則：根據(jù)匹配過程動態(tài)調(diào)整壞字符表和好后綴表，提高匹配效率。

2.組合規(guī)則：結(jié)合好后綴和壞字符規(guī)則，優(yōu)化模式串的移動策略。

（四）其他改進方法

1.哈希匹配：通過哈希函數(shù)快速判斷部分文本是否與模式串匹配，如Rabin-Karp算法。

2.貪心算法：在某些場景下，采用貪心策略減少不必要的比較，如基于字典序的匹配。

四、應(yīng)用場景與選擇

（一）應(yīng)用場景

1.文本編輯器：用于查找和替換文本中的特定字符串。

2.數(shù)據(jù)庫搜索：快速定位數(shù)據(jù)庫中的關(guān)鍵字段。

3.生物信息學(xué)：序列比對中的基因片段查找。

4.網(wǎng)絡(luò)安全：日志分析中的惡意代碼檢測。

（二）算法選擇

1.小規(guī)模數(shù)據(jù)或簡單場景：暴力匹配算法簡單易實現(xiàn)。

2.中大規(guī)模數(shù)據(jù)或性能要求高：KMP算法平衡效率與復(fù)雜度。

3.極高性能需求：Boyer-Moore算法在長文本匹配中表現(xiàn)優(yōu)異。

4.特定需求：結(jié)合哈?；虿⑿杏嬎?，進一步優(yōu)化性能。

五、總結(jié)

字符串匹配算法的改進是一個持續(xù)優(yōu)化的過程，根據(jù)不同的應(yīng)用需求和數(shù)據(jù)規(guī)模選擇合適的算法至關(guān)重要。通過預(yù)處理、規(guī)則優(yōu)化和并行計算等方法，可以顯著提升匹配效率，滿足實際應(yīng)用中的高性能要求。未來，隨著計算技術(shù)的發(fā)展，字符串匹配算法將更加智能化和高效化。

六、暴力匹配算法的詳細實現(xiàn)與局限性分析

（一）暴力匹配算法的偽代碼實現(xiàn)

FunctionBruteForceSearch(text,pattern):

n=Length(text)

m=Length(pattern)

i=0//text的起始比較位置索引

Whilei<=n-m

j=0//pattern的當(dāng)前比較位置索引

//比較text[i...i+m-1]和pattern[0...m-1]

Whilej<mANDtext[i+j]==pattern[j]

j=j+1

//如果j等于模式串長度m，則表示匹配成功

Ifj==m

Returni//返回匹配的起始位置

//如果不匹配，將text的起始比較位置向后移動一位

i=i+1

Return-1//如果遍歷完text仍未找到，返回-1表示未匹配

```

（二）暴力匹配算法的詳細步驟說明

1.初始化：首先，獲取文本串`text`和模式串`pattern`的長度，分別記為`n`和`m`。初始化文本串的起始比較索引`i`為0。

2.外層循環(huán)：使用`Whilei<=n-m`循環(huán)。這個循環(huán)控制文本串中用于與模式串比較的起始位置。如果`i`大于`n-m`，則模式串已經(jīng)無法完整地放在剩余的文本串中了，因此停止循環(huán)。

3.內(nèi)層比較：進入外層循環(huán)后，初始化模式串的比較索引`j`為0。使用`Whilej<mANDtext[i+j]==pattern[j]`循環(huán)，逐個字符比較當(dāng)前文本子串`text[i...i+m-1]`和模式串`pattern[0...m-1]`。

如果當(dāng)前字符`text[i+j]`等于`pattern[j]`，則`j`自增1，繼續(xù)比較下一個字符。

如果當(dāng)前字符不相等，或者比較已經(jīng)完成(`j`達到`m`)，內(nèi)層循環(huán)結(jié)束。

4.匹配成功判斷：在內(nèi)層循環(huán)結(jié)束后，檢查`j`是否等于`m`。如果等于`j==m`，說明模式串的所有字符都成功匹配了文本串的對應(yīng)部分，此時返回當(dāng)前的起始位置`i`，表示找到匹配。

5.匹配失敗或繼續(xù)搜索：如果`j`不等于`m`，說明在當(dāng)前位置`i`處匹配失?。ú糠制ヅ浠蛲耆黄ヅ洌?。此時，需要將文本串的起始比較位置向后移動一位，即`i=i+1`，然后回到外層循環(huán)的判斷條件，繼續(xù)尋找下一個可能的匹配位置。

6.全文遍歷完畢：如果外層循環(huán)正常結(jié)束（即`i`超過了`n-m`），且整個過程中從未返回匹配位置，則說明整個文本串中都不存在模式串，返回`-1`表示未找到。

（三）暴力匹配算法的局限性分析

1.時間復(fù)雜度低：暴力匹配算法在最壞情況下的時間復(fù)雜度為O(nm)。具體表現(xiàn)為，當(dāng)文本串與模式串完全不匹配，或者模式串位于文本串的每個字符之后時，每次比較都會進行`m`次字符比較，且需要執(zhí)行`n-m+1`次這樣的比較過程。例如，在文本"aaaaaaaaa"中查找模式串"aaab"，會進行9次完整的4字符比較（假設(shè)模式串長度為4），每次比較都進行4次失敗比較，總共36次比較。

2.效率低下：由于缺乏預(yù)處理和優(yōu)化策略，暴力匹配算法在處理長文本和復(fù)雜模式串時效率非常低。每次不匹配都需要從頭開始或移動很短的距離重新比較，導(dǎo)致大量的無效操作。

3.對重復(fù)模式敏感：當(dāng)模式串在文本串中出現(xiàn)多次時，暴力匹配會為每次出現(xiàn)都進行完整的比較過程，無法利用之前匹配的信息進行優(yōu)化。雖然可以通過記錄匹配位置后跳過某些部分來略微改進，但基本邏輯仍是逐個比較。

4.缺乏靈活性：暴力匹配算法本身不包含任何高級的匹配策略，如壞字符跳過、好后綴利用等，難以適應(yīng)需要快速失敗或高效查找的特定場景。

七、KMP算法的詳細實現(xiàn)與Next數(shù)組構(gòu)建

（一）KMP算法的核心思想與優(yōu)勢

KMP算法（Knuth-Morris-Pratt）通過預(yù)處理模式串，構(gòu)建一個部分匹配表（通常稱為Next數(shù)組或失配函數(shù)），來避免在文本串匹配失敗后進行不必要的回溯。其核心思想是：當(dāng)文本串中的字符與模式串不匹配時，模式串本身應(yīng)該盡可能地向右移動，移動的距離取決于模式串自身的前后綴匹配程度。這樣，已經(jīng)比較過的字符就不需要重新比較了。

KMP算法的主要優(yōu)勢在于其最壞情況下的時間復(fù)雜度為O(n+m)，相較于暴力匹配的O(nm)有顯著提升，且空間復(fù)雜度也較為可控（通常為O(m)）。

（二）Next數(shù)組的構(gòu)建（KMP預(yù)處理步驟）

Next數(shù)組是KMP算法的關(guān)鍵，它記錄了模式串中每個位置`k`（從0開始）之后的最長相同前后綴的長度。構(gòu)建Next數(shù)組的過程如下：

1.初始化：創(chuàng)建一個長度為`m`的數(shù)組`Next`，初始化`Next[0]=0`。因為單個字符的前后綴長度為0。

2.迭代構(gòu)建：設(shè)置兩個指針`i`和`k`，初始時`i=1`（指向模式串的第二個字符），`k=0`（指向`Next`數(shù)組的當(dāng)前計算位置，即`Next[i-1]`）。

3.比較與賦值：進入一個循環(huán)，直到`i`達到模式串長度`m`。

比較模式串的第`k`個字符`pattern[k]`和第`i`個字符`pattern[i]`。

情況一：匹配(`pattern[k]==pattern[i]`)。如果當(dāng)前字符匹配，說明從`k+1`到`i`的子串與模式串的前`k+1`個字符的最長相同前后綴長度為`k+1`。因此，設(shè)置`Next[i]=k+1`。然后，將`i`和`k`都向右移動一位（`i=i+1`,`k=k+1`），繼續(xù)比較下一個字符對。

情況二：不匹配(`pattern[k]!=pattern[i]`)。如果不匹配，我們需要利用已經(jīng)計算出的`Next`數(shù)組信息來確定新的`k`值，以避免從頭開始比較。將`k`設(shè)置為`Next[k]`。注意，這里`Next[k]`表示的是`pattern[0...k-1]`這個子串的最長相同前后綴長度。然后，再次比較`pattern[k]`和`pattern[i]`。

如果此時`k==0`（即`Next[k]`為0），說明當(dāng)前字符`pattern[i]`與模式串的第一個字符不匹配，且沒有更長的前后綴可以利用。此時，設(shè)置`Next[i]=0`，并將`i`向右移動一位（`i=i+1`）。

如果`k`不為0，則回到情況二的第一步，比較`pattern[k]`和`pattern[i]`。

4.完成構(gòu)建：當(dāng)`i`從1遍歷到`m-1`后，`Next`數(shù)組構(gòu)建完成。

Next數(shù)組的示例：

假設(shè)模式串`pattern="ABCDABD"`，其長度`m=7`。

構(gòu)建過程：

-`Next[0]=0`

-`i=1`(pattern[1]='B'),`k=0`:

-`pattern[0]='A'`!=`pattern[1]='B'`,`k=Next[0]=0`

-`k=0`,`Next[1]=0`

-`i=2`(pattern[2]='C'),`k=0`:

-`pattern[0]='A'`!=`pattern[2]='C'`,`k=Next[0]=0`

-`k=0`,`Next[2]=0`

-`i=3`(pattern[3]='D'),`k=0`:

-`pattern[0]='A'`!=`pattern[3]='D'`,`k=Next[0]=0`

-`k=0`,`Next[3]=0`

-`i=4`(pattern[4]='A'),`k=0`:

-`pattern[0]='A'`==`pattern[4]='A'`,`Next[4]=k+1=1`

-`i=5`,`k=1`

-`i=5`(pattern[5]='B'),`k=1`:

-`pattern[1]='B'`==`pattern[5]='B'`,`Next[5]=k+1=2`

-`i=6`,`k=2`

-`i=6`(pattern[6]='D'),`k=2`:

-`pattern[2]='C'`!=`pattern[6]='D'`,`k=Next[2]=0`

-`k=0`,`Next[6]=0`

-`i=7`(結(jié)束)

最終`Next=[0,0,0,0,1,2,0]`

（三）KMP算法的匹配過程

使用構(gòu)建好的`Next`數(shù)組，可以在文本串中高效地查找模式串：

1.初始化：獲取文本串`text`和模式串`pattern`的長度`n`和`m`。初始化文本串指針`i`為0，模式串指針`j`為0。

2.匹配循環(huán)：使用`Whilei<n`循環(huán)。循環(huán)中執(zhí)行以下步驟：

比較：比較`text[i]`和`pattern[j]`。

匹配成功：如果`text[i]==pattern[j]`，則`i`和`j`都自增1（`i=i+1`,`j=j+1`），繼續(xù)比較下一個字符。

匹配失?。喝绻鸴text[i]!=pattern[j]`，則需要利用`Next`數(shù)組移動模式串。設(shè)置`k=Next[j]`。

將模式串指針`j`移動到`k`的位置（`j=k`）。

比較文本串的當(dāng)前字符`text[i]`和模式串的`pattern[j]`。

如果相等，`i`和`j`都自增1。

如果不相等，重復(fù)上述步驟，即`k=Next[j]`，然后比較`text[i]`和`pattern[j]`。

這個過程會一直進行，直到`j`回到0或者找到一個相等的字符。

循環(huán)繼續(xù)：無論匹配成功還是利用`Next`數(shù)組調(diào)整后繼續(xù)比較，只要`j`不等于模式串長度`m`，就繼續(xù)外層循環(huán)，比較`text[i+1]`和`pattern[j+1]`。

3.匹配完成：如果內(nèi)層比較循環(huán)結(jié)束時`j==m`，說明成功匹配，返回起始位置`i-j`（因為`i`和`j`在匹配過程中都自增了`m`次）。

4.全文遍歷完畢：如果外層循環(huán)結(jié)束仍未找到匹配（即`i`超過了`n`），則返回`-1`。

KMP匹配過程的示例（續(xù)上例）：

文本串`text="ABCDABCDABD"`，模式串`pattern="ABCDABD"`，`Next=[0,0,0,0,1,2,0]`。

-`i=0`,`j=0`:'A'=='A',`i=1`,`j=1`

-`i=1`,`j=1`:'B'=='B',`i=2`,`j=2`

-`i=2`,`j=2`:'C'=='C',`i=3`,`j=3`

-`i=3`,`j=3`:'D'=='D',`i=4`,`j=4`

-`i=4`,`j=4`:'A'=='A',`i=5`,`j=5`

-`i=5`,`j=5`:'B'=='B',`i=6`,`j=6`

-`i=6`,`j=6`:'C'!='D'(不匹配),`k=Next[6]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0

一、字符串匹配算法概述

字符串匹配算法是計算機科學(xué)中常用的算法之一，主要用于在一個較長的文本串（文本）中查找一個較短的模式串（模式）是否存在及其位置。根據(jù)不同的應(yīng)用場景和性能需求，有多種字符串匹配算法被提出，如暴力匹配、KMP算法、Boyer-Moore算法等。本手冊旨在介紹幾種常見的字符串匹配算法，并探討其改進方法。

二、常見字符串匹配算法

（一）暴力匹配算法

1.原理：暴力匹配算法是最簡單的字符串匹配方法，通過逐個字符比較模式串和文本串，若不匹配則模式串向右移動一個字符，直到找到匹配或遍歷完文本。

2.步驟：

(1)從文本串的第一個字符開始，與模式串的第一個字符比較。

(2)若所有字符匹配，返回匹配位置；若不匹配，模式串向右移動一位，重新比較。

(3)重復(fù)步驟(2)，直到匹配成功或文本串遍歷完畢。

3.時間復(fù)雜度：最壞情況下為O(nm)，其中n是文本串長度，m是模式串長度。

（二）KMP算法

1.原理：KMP算法通過預(yù)處理模式串，構(gòu)建部分匹配表（Next數(shù)組），避免暴力匹配中的無效回溯。

2.步驟：

(1)構(gòu)建Next數(shù)組：計算模式串中每個前綴的最長相同前后綴長度。

(2)匹配過程：

a.從文本串和模式串的第一個字符開始比較。

b.若匹配，指針均向右移動一位；若不匹配，利用Next數(shù)組確定模式串的移動位置。

c.重復(fù)步驟b，直到匹配成功或文本串遍歷完畢。

3.時間復(fù)雜度：O(n+m)，顯著優(yōu)于暴力匹配。

（三）Boyer-Moore算法

1.原理：Boyer-Moore算法通過好后綴規(guī)則和壞字符規(guī)則，從文本串的末尾開始匹配，減少比較次數(shù)。

2.步驟：

(1)構(gòu)建壞字符表和好后綴表：

a.壞字符表記錄模式串中每個字符在模式串中最右側(cè)的位置。

b.好后綴表記錄模式串中每個后綴的最長相同前綴長度。

(2)匹配過程：

a.從文本串的末尾開始，與模式串的末尾字符比較。

b.若匹配，指針均向左移動一位；若不匹配，根據(jù)壞字符規(guī)則或好后綴規(guī)則移動模式串位置。

c.重復(fù)步驟b，直到匹配成功或文本串遍歷完畢。

3.時間復(fù)雜度：最佳情況下為O(n/m)，但最壞情況下仍為O(nm)。

三、字符串匹配算法的改進方法

（一）優(yōu)化暴力匹配算法

1.提前終止：若文本串中包含多個模式串實例，可提前終止搜索以節(jié)省時間。

2.字符預(yù)處理：對文本串和模式串進行編碼或哈希，減少比較開銷。

（二）KMP算法的改進

1.改進Next數(shù)組：使用更高效的方法構(gòu)建Next數(shù)組，如利用動態(tài)規(guī)劃。

2.并行匹配：在多核環(huán)境下，可將文本串分塊并行處理，加速匹配過程。

（三）Boyer-Moore算法的改進

1.動態(tài)更新規(guī)則：根據(jù)匹配過程動態(tài)調(diào)整壞字符表和好后綴表，提高匹配效率。

2.組合規(guī)則：結(jié)合好后綴和壞字符規(guī)則，優(yōu)化模式串的移動策略。

（四）其他改進方法

1.哈希匹配：通過哈希函數(shù)快速判斷部分文本是否與模式串匹配，如Rabin-Karp算法。

2.貪心算法：在某些場景下，采用貪心策略減少不必要的比較，如基于字典序的匹配。

四、應(yīng)用場景與選擇

（一）應(yīng)用場景

1.文本編輯器：用于查找和替換文本中的特定字符串。

2.數(shù)據(jù)庫搜索：快速定位數(shù)據(jù)庫中的關(guān)鍵字段。

3.生物信息學(xué)：序列比對中的基因片段查找。

4.網(wǎng)絡(luò)安全：日志分析中的惡意代碼檢測。

（二）算法選擇

1.小規(guī)模數(shù)據(jù)或簡單場景：暴力匹配算法簡單易實現(xiàn)。

2.中大規(guī)模數(shù)據(jù)或性能要求高：KMP算法平衡效率與復(fù)雜度。

3.極高性能需求：Boyer-Moore算法在長文本匹配中表現(xiàn)優(yōu)異。

4.特定需求：結(jié)合哈?；虿⑿杏嬎?，進一步優(yōu)化性能。

五、總結(jié)

字符串匹配算法的改進是一個持續(xù)優(yōu)化的過程，根據(jù)不同的應(yīng)用需求和數(shù)據(jù)規(guī)模選擇合適的算法至關(guān)重要。通過預(yù)處理、規(guī)則優(yōu)化和并行計算等方法，可以顯著提升匹配效率，滿足實際應(yīng)用中的高性能要求。未來，隨著計算技術(shù)的發(fā)展，字符串匹配算法將更加智能化和高效化。

六、暴力匹配算法的詳細實現(xiàn)與局限性分析

（一）暴力匹配算法的偽代碼實現(xiàn)

FunctionBruteForceSearch(text,pattern):

n=Length(text)

m=Length(pattern)

i=0//text的起始比較位置索引

Whilei<=n-m

j=0//pattern的當(dāng)前比較位置索引

//比較text[i...i+m-1]和pattern[0...m-1]

Whilej<mANDtext[i+j]==pattern[j]

j=j+1

//如果j等于模式串長度m，則表示匹配成功

Ifj==m

Returni//返回匹配的起始位置

//如果不匹配，將text的起始比較位置向后移動一位

i=i+1

Return-1//如果遍歷完text仍未找到，返回-1表示未匹配

```

（二）暴力匹配算法的詳細步驟說明

1.初始化：首先，獲取文本串`text`和模式串`pattern`的長度，分別記為`n`和`m`。初始化文本串的起始比較索引`i`為0。

2.外層循環(huán)：使用`Whilei<=n-m`循環(huán)。這個循環(huán)控制文本串中用于與模式串比較的起始位置。如果`i`大于`n-m`，則模式串已經(jīng)無法完整地放在剩余的文本串中了，因此停止循環(huán)。

3.內(nèi)層比較：進入外層循環(huán)后，初始化模式串的比較索引`j`為0。使用`Whilej<mANDtext[i+j]==pattern[j]`循環(huán)，逐個字符比較當(dāng)前文本子串`text[i...i+m-1]`和模式串`pattern[0...m-1]`。

如果當(dāng)前字符`text[i+j]`等于`pattern[j]`，則`j`自增1，繼續(xù)比較下一個字符。

如果當(dāng)前字符不相等，或者比較已經(jīng)完成(`j`達到`m`)，內(nèi)層循環(huán)結(jié)束。

4.匹配成功判斷：在內(nèi)層循環(huán)結(jié)束后，檢查`j`是否等于`m`。如果等于`j==m`，說明模式串的所有字符都成功匹配了文本串的對應(yīng)部分，此時返回當(dāng)前的起始位置`i`，表示找到匹配。

5.匹配失敗或繼續(xù)搜索：如果`j`不等于`m`，說明在當(dāng)前位置`i`處匹配失?。ú糠制ヅ浠蛲耆黄ヅ洌?。此時，需要將文本串的起始比較位置向后移動一位，即`i=i+1`，然后回到外層循環(huán)的判斷條件，繼續(xù)尋找下一個可能的匹配位置。

6.全文遍歷完畢：如果外層循環(huán)正常結(jié)束（即`i`超過了`n-m`），且整個過程中從未返回匹配位置，則說明整個文本串中都不存在模式串，返回`-1`表示未找到。

（三）暴力匹配算法的局限性分析

1.時間復(fù)雜度低：暴力匹配算法在最壞情況下的時間復(fù)雜度為O(nm)。具體表現(xiàn)為，當(dāng)文本串與模式串完全不匹配，或者模式串位于文本串的每個字符之后時，每次比較都會進行`m`次字符比較，且需要執(zhí)行`n-m+1`次這樣的比較過程。例如，在文本"aaaaaaaaa"中查找模式串"aaab"，會進行9次完整的4字符比較（假設(shè)模式串長度為4），每次比較都進行4次失敗比較，總共36次比較。

2.效率低下：由于缺乏預(yù)處理和優(yōu)化策略，暴力匹配算法在處理長文本和復(fù)雜模式串時效率非常低。每次不匹配都需要從頭開始或移動很短的距離重新比較，導(dǎo)致大量的無效操作。

3.對重復(fù)模式敏感：當(dāng)模式串在文本串中出現(xiàn)多次時，暴力匹配會為每次出現(xiàn)都進行完整的比較過程，無法利用之前匹配的信息進行優(yōu)化。雖然可以通過記錄匹配位置后跳過某些部分來略微改進，但基本邏輯仍是逐個比較。

4.缺乏靈活性：暴力匹配算法本身不包含任何高級的匹配策略，如壞字符跳過、好后綴利用等，難以適應(yīng)需要快速失敗或高效查找的特定場景。

七、KMP算法的詳細實現(xiàn)與Next數(shù)組構(gòu)建

（一）KMP算法的核心思想與優(yōu)勢

KMP算法（Knuth-Morris-Pratt）通過預(yù)處理模式串，構(gòu)建一個部分匹配表（通常稱為Next數(shù)組或失配函數(shù)），來避免在文本串匹配失敗后進行不必要的回溯。其核心思想是：當(dāng)文本串中的字符與模式串不匹配時，模式串本身應(yīng)該盡可能地向右移動，移動的距離取決于模式串自身的前后綴匹配程度。這樣，已經(jīng)比較過的字符就不需要重新比較了。

KMP算法的主要優(yōu)勢在于其最壞情況下的時間復(fù)雜度為O(n+m)，相較于暴力匹配的O(nm)有顯著提升，且空間復(fù)雜度也較為可控（通常為O(m)）。

（二）Next數(shù)組的構(gòu)建（KMP預(yù)處理步驟）

Next數(shù)組是KMP算法的關(guān)鍵，它記錄了模式串中每個位置`k`（從0開始）之后的最長相同前后綴的長度。構(gòu)建Next數(shù)組的過程如下：

1.初始化：創(chuàng)建一個長度為`m`的數(shù)組`Next`，初始化`Next[0]=0`。因為單個字符的前后綴長度為0。

2.迭代構(gòu)建：設(shè)置兩個指針`i`和`k`，初始時`i=1`（指向模式串的第二個字符），`k=0`（指向`Next`數(shù)組的當(dāng)前計算位置，即`Next[i-1]`）。

3.比較與賦值：進入一個循環(huán)，直到`i`達到模式串長度`m`。

比較模式串的第`k`個字符`pattern[k]`和第`i`個字符`pattern[i]`。

情況一：匹配(`pattern[k]==pattern[i]`)。如果當(dāng)前字符匹配，說明從`k+1`到`i`的子串與模式串的前`k+1`個字符的最長相同前后綴長度為`k+1`。因此，設(shè)置`Next[i]=k+1`。然后，將`i`和`k`都向右移動一位（`i=i+1`,`k=k+1`），繼續(xù)比較下一個字符對。

情況二：不匹配(`pattern[k]!=pattern[i]`)。如果不匹配，我們需要利用已經(jīng)計算出的`Next`數(shù)組信息來確定新的`k`值，以避免從頭開始比較。將`k`設(shè)置為`Next[k]`。注意，這里`Next[k]`表示的是`pattern[0...k-1]`這個子串的最長相同前后綴長度。然后，再次比較`pattern[k]`和`pattern[i]`。

如果此時`k==0`（即`Next[k]`為0），說明當(dāng)前字符`pattern[i]`與模式串的第一個字符不匹配，且沒有更長的前后綴可以利用。此時，設(shè)置`Next[i]=0`，并將`i`向右移動一位（`i=i+1`）。

如果`k`不為0，則回到情況二的第一步，比較`pattern[k]`和`pattern[i]`。

4.完成構(gòu)建：當(dāng)`i`從1遍歷到`m-1`后，`Next`數(shù)組構(gòu)建完成。

Next數(shù)組的示例：

假設(shè)模式串`pattern="ABCDABD"`，其長度`m=7`。

構(gòu)建過程：

-`Next[0]=0`

-`i=1`(pattern[1]='B'),`k=0`:

-`pattern[0]='A'`!=`pattern[1]='B'`,`k=Next[0]=0`

-`k=0`,`Next[1]=0`

-`i=2`(pattern[2]='C'),`k=0`:

-`pattern[0]='A'`!=`pattern[2]='C'`,`k=Next[0]=0`

-`k=0`,`Next[2]=0`

-`i=3`(pattern[3]='D'),`k=0`:

-`pattern[0]='A'`!=`pattern[3]='D'`,`k=Next[0]=0`

-`k=0`,`Next[3]=0`

-`i=4`(pattern[4]='A'),`k=0`:

-`pattern[0]='A'`==`pattern[4]='A'`,`Next[4]=k+1=1`

-`i=5`,`k=1`

-`i=5`(pattern[5]='B'),`k=1`:

-`pattern[1]='B'`==`pattern[5]='B'`,`Next[5]=k+1=2`

-`i=6`,`k=2`

-`i=6`(pattern[6]='D'),`k=2`:

-`pattern[2]='C'`!=`pattern[6]='D'`,`k=Next[2]=0`

-`k=0`,`Next[6]=0`

-`i=7`(結(jié)束)

最終`Next=[0,0,0,0,1,2,0]`

（三）KMP算法的匹配過程

使用構(gòu)建好的`Next`數(shù)組，可以在文本串中高效地查找模式串：

1.初始化：獲取文本串`text`和模式串`pattern`的長度`n`和`m`。初始化文本串指針`i`為0，模式串指針`j`為0。

2.匹配循環(huán)：使用`Whilei<n`循環(huán)。循環(huán)中執(zhí)行以下步驟：

比較：比較`text[i]`和`pattern[j]`。

匹配成功：如果`text[i]==pattern[j]`，則`i`和`j`都自增1（`i=i+1`,`j=j+1`），繼續(xù)比較下一個字符。

匹配失?。喝绻鸴text[i]!=pattern[j]`，則需要利用`Next`數(shù)組移動模式串。設(shè)置`k=Next[j]`。

將模式串指針`j`移動到`k`的位置（`j=k`）。

比較文本串的當(dāng)前字符`text[i]`和模式串的`pattern[j]`。

如果相等，`i`和`j`都自增1。

如果不相等，重復(fù)上述步驟，即`k=Next[j]`，然后比較`text[i]`和`pattern[j]`。

這個過程會一直進行，直到`j`回到0或者找到一個相等的字符。

循環(huán)繼續(xù)：無論匹配成功還是利用`Next`數(shù)組調(diào)整后繼續(xù)比較，只要`j`不等于模式串長度`m`，就繼續(xù)外層循環(huán)，比較`text[i+1]`和`pattern[j+1]`。

3.匹配完成：如果內(nèi)層比較循環(huán)結(jié)束時`j==m`，說明成功匹配，返回起始位置`i-j`（因為`i`和`j`在匹配過程中都自增了`m`次）。

4.全文遍歷完畢：如果外層循環(huán)結(jié)束仍未找到匹配（即`i`超過了`n`），則返回`-1`。

KMP匹配過程的示例（續(xù)上例）：

文本串`text="ABCDABCDABD"`，模式串`pattern="ABCDABD"`，`Next=[0,0,0,0,1,2,0]`。

-`i=0`,`j=0`:'A'=='A',`i=1`,`j=1`

-`i=1`,`j=1`:'B'=='B',`i=2`,`j=2`

-`i=2`,`j=2`:'C'=='C',`i=3`,`j=3`

-`i=3`,`j=3`:'D'=='D',`i=4`,`j=4`

-`i=4`,`j=4`:'A'=='A',`i=5`,`j=5`

-`i=5`,`j=5`:'B'=='B',`i=6`,`j=6`

-`i=6`,`j=6`:'C'!='D'(不匹配),`k=Next[6]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`:'C'!='A'(不匹配),`k=Next[0]=0`

-`j=0`

-`i=6`,`j=0`: