字符串匹配算法的模式匹配原理一、引言

字符串匹配算法是計算機科學中常見的算法問題，其核心目標是在一個較長的文本串（主串）中查找是否存在一個較短的子串（模式串），并返回子串在主串中的起始位置。模式匹配原理涉及多種方法，包括樸素匹配、KMP算法、Boyer-Moore算法等。本文檔將重點介紹樸素匹配算法和KMP算法的基本原理、實現(xiàn)步驟及優(yōu)缺點分析。

二、樸素匹配算法（Brute-ForceAlgorithm）

樸素匹配算法是最直觀的字符串匹配方法，其基本思想是：從主串和模式串的第一個字符開始，依次比較兩個串的字符是否相同，若相同則繼續(xù)比較下一個字符，若不同則主串指針回退到上一個匹配位置的后一個字符，模式串指針回退到第一個字符，重新開始匹配。

（一）算法步驟

1.初始化：設置主串指針`i`從0開始，模式串指針`j`也從0開始。

2.匹配過程：

-比較`text[i]`和`pattern[j]`是否相同。

-若相同，`i`和`j`均加1，繼續(xù)比較下一個字符。

-若不同，`i`回退到`i-j+1`，`j`重置為0。

3.終止條件：

-若`j`達到模式串長度`m`，則匹配成功，返回`i-m`（匹配起始位置）。

-若`i`超過主串長度`n`仍未匹配成功，則匹配失敗，返回-1。

（二）示例

假設主串`text="ABCDABCDABE"`，模式串`pattern="ABCDABE"`：

1.初始：`i=0,j=0`，比較`'A'=='A'`，`i=1,j=1`，比較`'B'=='B'`，...

2.到`i=9,j=8`時，`'E'!='E'`，回退`i=5,j=0`，重新匹配。

3.最終匹配成功，起始位置為5。

（三）時間復雜度

-最好情況：O(n)，模式串第一個字符即匹配成功。

-最壞情況：O(nm)，模式串每個字符均需比較。

-平均情況：O(nm)。

三、KMP算法（Knuth-Morris-Pratt）

KMP算法是對樸素匹配的優(yōu)化，通過預處理模式串，避免主串指針的無效回退，從而將時間復雜度降低至O(n)。

（一）核心思想

KMP算法的核心是構建一個“部分匹配表”（Next數(shù)組），用于記錄模式串的前綴和后綴相同長度的最大值。當不匹配發(fā)生時，利用該表跳過已知的無效前綴，直接從有效位置繼續(xù)匹配。

（二）Next數(shù)組構建

Next數(shù)組的計算步驟如下：

1.初始化：`next[0]=-1`，`next[1]=0`。

2.從`i=2`開始，遍歷模式串：

-若`pattern[i-1]==pattern[next[i-1]]`，則`next[i]=next[i-1]+1`。

-否則，回退`k=next[next[i-1]]`，比較`pattern[i-1]==pattern[k]`，重復直到找到匹配或`k=-1`。

-若無匹配，`next[i]=0`。

示例：模式串`"ABCDABE"`的Next數(shù)組為`[-1,0,0,0,1,2,3]`。

（三）匹配過程

1.初始化：主串指針`i=0`，模式串指針`j=0`。

2.比較`text[i]`和`pattern[j]`：

-若相同，`i++,j++`。

-若`j==m`，匹配成功，返回`i-j`。

-若不匹配且`j>0`，更新`j=next[j]`（利用Next數(shù)組跳轉）。

-若`j==0`，`i++`繼續(xù)匹配。

3.匹配失敗返回-1。

（四）時間復雜度

-構建Next數(shù)組：O(m)。

-匹配過程：O(n)。

-總體時間復雜度：O(n+m)。

四、Boyer-Moore算法簡介

Boyer-Moore算法是另一種高效的模式匹配算法，其核心思想是通過“壞字符規(guī)則”和“好后綴規(guī)則”跳過大量無效比較，時間復雜度可達O(n/m)。

-壞字符規(guī)則：基于模式串中不匹配的字符，計算最大可跳轉距離。

-好后綴規(guī)則：基于模式串中匹配的后綴，計算最大可跳轉距離。

Boyer-Moore算法適用于長模式串，但實現(xiàn)相對復雜，此處不作詳細展開。

五、總結

字符串匹配算法的選擇取決于實際應用場景：

-樸素匹配：簡單易實現(xiàn)，適用于小規(guī)模數(shù)據(jù)。

-KMP算法：通用性強，效率高，適合大規(guī)模文本處理。

-Boyer-Moore算法：速度最快，但實現(xiàn)復雜，適用于長模式串。

三、KMP算法（Knuth-Morris-Pratt）

KMP算法是對樸素匹配的優(yōu)化，通過預處理模式串，避免主串指針的無效回退，從而將時間復雜度降低至O(n)。其核心在于利用模式串自身的特性，在發(fā)生不匹配時，盡可能多地跳過已經(jīng)確認不會匹配的部分，從而提高匹配效率。KMP算法主要由兩部分組成：部分匹配表的構建（Next數(shù)組的生成）和基于部分匹配表的匹配過程。

（一）核心思想與優(yōu)勢

KMP算法的核心思想是：當模式串與主串在某位置發(fā)生不匹配時，不需要將主串的指針回退到模式串指針之前的位置，而是利用已經(jīng)計算出的模式串的部分匹配信息，將模式串向后滑動，使其在主串中的某個位置與之前匹配成功的部分對齊，從而繼續(xù)比較。這種做法避免了主串指針的多次回退，顯著提高了算法的效率。

KMP算法的優(yōu)勢主要體現(xiàn)在以下方面：

1.時間效率高：在最好和平均情況下，時間復雜度為O(n)，遠優(yōu)于樸素匹配的O(nm)。

2.空間復雜度可控：Next數(shù)組的構建需要額外的空間，但其空間復雜度為O(m)，其中m是模式串的長度。

3.通用性強：適用于多種字符串匹配場景，特別是當模式串較長或主串中存在大量重復子串時，性能優(yōu)勢更為明顯。

（二）部分匹配表（Next數(shù)組）的構建

部分匹配表是KMP算法的關鍵，它記錄了模式串的前綴和后綴的最長相同子串的長度。通過該表，可以在不匹配發(fā)生時，確定模式串應該滑動的位置。部分匹配表的構建過程如下：

1.初始化：

-創(chuàng)建一個與模式串等長的數(shù)組`Next`，用于存儲部分匹配信息。

-初始化`Next[0]=-1`，因為單個字符的前綴和后綴不可能相同。

-設置指針`i`從1開始遍歷模式串，`k`為當前`i`的前一個位置的最長相同子串長度（即`Next[k]`）。

2.遍歷模式串，填充Next數(shù)組：

-對于每個位置`i`（從1到m-1），執(zhí)行以下步驟：

(1)比較當前字符與前綴的最長相同子串的最后一個字符：

-若`pattern[i-1]==pattern[k]`，則說明當前前綴和后綴的最長相同子串長度加1，即`Next[i]=k+1`，然后`i++`和`k++`繼續(xù)比較下一個字符。

-若不匹配，則需要更新`k`的值：將`k`設置為`Next[k-1]`，即回退到前一個最長相同子串的前一個位置，重復比較，直到`k==-1`或`pattern[i-1]==pattern[k]`。

(2)處理不匹配的情況：

-若`k==-1`，說明當前字符`pattern[i-1]`沒有前綴和后綴相同的情況，因此`Next[i]=0`，然后`i++`繼續(xù)遍歷。

(3)更新Next數(shù)組：

-每次比較后，若找到匹配，則`Next[i]=k+1`；若未找到，則`Next[i]=0`（當`k==-1`時）。

3.Next數(shù)組的含義：

-`Next[i]`表示模式串`pattern[0...i-1]`中，最長相等的前綴和后綴的長度。

-例如，模式串`"ABCDABE"`的Next數(shù)組為`[-1,0,0,0,1,2,3]`，表示：

-`pattern[0]`："A"→無前綴和后綴相同，`Next[0]=-1`。

-`pattern[0...1]`："AB"→無相同子串，`Next[1]=0`。

-`pattern[0...3]`："ABCD"→無相同子串，`Next[3]=0`。

-`pattern[0...4]`："ABCDAB"→"AB"=="AB"，`Next[4]=1`。

-`pattern[0...5]`："ABCDABE"→"AB"=="AB"，`Next[5]=2`。

-`pattern[0...6]`："ABCDABE"→"ABCD"=="ABCD"，`Next[6]=3`。

（三）基于部分匹配表的匹配過程

在構建完Next數(shù)組后，即可開始匹配過程。匹配過程中，主串指針`i`和模式串指針`j`分別從0開始遍歷，當字符匹配時，兩者同時后移；當不匹配時，利用Next數(shù)組確定模式串的滑動位置。具體步驟如下：

1.初始化：

-設置主串指針`i=0`，模式串指針`j=0`。

2.遍歷主串和模式串：

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

(1)若相同：

-`i++`，`j++`，繼續(xù)比較下一個字符。

-若`j==m`（模式串長度），則匹配成功，返回`i-j`（匹配起始位置）。

(2)若不同：

-若`j>0`，則將模式串指針`j`更新為`Next[j]`，即利用Next數(shù)組跳轉。

-若`j==0`，說明當前匹配失敗，僅移動主串指針`i++`，繼續(xù)匹配下一個位置。

3.匹配失?。?/p>

-若遍歷完主串仍未匹配成功（即`i==n`且未返回匹配位置），則返回-1表示不存在匹配。

4.示例：

-主串`text="ABCDABCDABE"`，模式串`pattern="ABCDABE"`，Next數(shù)組為`[-1,0,0,0,1,2,3]`。

-匹配過程：

-`i=0,j=0`，比較`'A'=='A'`，`i=1,j=1`。

-`i=2,j=2`，比較`'B'=='B'`，`i=3,j=3`。

-`i=4,j=4`，比較`'C'=='C'`，`i=5,j=5`。

-`i=6,j=6`，比較`'D'=='D'`，`i=7,j=7`。

-`i=8,j=8`，比較`'A'!='E'`，`j`更新為`Next[8]=3`（跳轉至`'CDABE'`）。

-`i=8,j=3`，比較`'A'=='A'`，`i=9,j=4`。

-`i=10,j=5`，比較`'B'=='B'`，`i=11,j=6`。

-`i=12,j=7`，比較`'E'=='E'`，`j==m`，匹配成功，返回`i-j=5`。

（四）時間復雜度分析

1.Next數(shù)組的構建：

-遍歷模式串一次，每次比較和更新Next數(shù)組的時間復雜度為O(1)，因此總時間復雜度為O(m)。

2.匹配過程：

-主串和模式串各遍歷一次，每次比較和指針更新操作的時間復雜度為O(1)，因此總時間復雜度為O(n)。

3.總體時間復雜度：

-O(m)+O(n)=O(n+m)，即線性時間復雜度。

（五）空間復雜度分析

-Next數(shù)組占用O(m)的額外空間，因此KMP算法的空間復雜度為O(m)。

（六）適用場景

KMP算法適用于以下場景：

1.模式串較長：當模式串長度m較大時，KMP算法的效率優(yōu)勢明顯。

2.主串中存在大量重復子串：KMP算法能夠有效利用重復子串的信息，減少不必要的比較。

3.需要多次匹配同一模式串：Next數(shù)組的預處理可以在多次匹配時復用，提高效率。

四、Boyer-Moore算法簡介

Boyer-Moore算法是另一種高效的字符串匹配算法，其核心思想是通過“壞字符規(guī)則”和“好后綴規(guī)則”跳過大量無效比較，時間復雜度可達O(n/m)。該算法在模式串較長時表現(xiàn)優(yōu)異，但實現(xiàn)相對復雜，因此此處僅作簡要介紹。

（一）壞字符規(guī)則（BadCharacterRule）

壞字符規(guī)則基于模式串中不匹配的字符，計算模式串可以滑動的最大距離。具體步驟如下：

1.壞字符表構建：

-創(chuàng)建一個壞字符表，記錄模式串中每個字符最后出現(xiàn)的位置。若字符未出現(xiàn)，則記錄為-1。

2.匹配過程中的壞字符處理：

-當主串和模式串在某位置不匹配時，找到模式串中與主串不匹配的字符（壞字符）。

-根據(jù)壞字符表，計算模式串可滑動的距離：

-若壞字符在模式串中不存在（位置為-1），則模式串可以滑動到主串的下一個位置。

-若壞字符存在，則模式串滑動到壞字符在主串中的位置之后。

-若壞字符在模式串中有多個，則選擇最右邊的壞字符進行滑動。

3.示例：

-模式串`"ABCDABE"`，壞字符表：`{'A':6,'B':5,'C':4,'D':3,'E':7,'F':-1}`。

-主串`"ABCDABCDABE"`，模式串滑動到`"ABCDABE"`時，`'E'`不匹配（壞字符為`'E'`，最后出現(xiàn)位置為7），模式串滑動到`'E'`之后，即從`"BCDABE"`開始繼續(xù)匹配。

（二）好后綴規(guī)則（GoodSuffixRule）

好后綴規(guī)則基于模式串中匹配的后綴，計算模式串可以滑動的最大距離。該規(guī)則比壞字符規(guī)則更復雜，但可以跳過更多的無效比較。

1.好后綴表構建：

-創(chuàng)建一個好后綴表，記錄模式串中每個后綴的最長相等前綴和后綴的長度。

2.匹配過程中的好后綴處理：

-當主串和模式串在某位置不匹配時，若不匹配位置之前的部分與模式串的后綴相同，則利用好后綴表確定模式串的滑動位置。

-具體滑動距離取決于好后綴表中記錄的最長相等子串長度。

3.示例：

-模式串`"ABCDABE"`，好后綴表：`{-1,0,0,0,1,2,3}`（與KMP的Next數(shù)組類似，但含義不同）。

-主串`"ABCDABCDABE"`，模式串滑動到`"ABCDABE"`時，若`'E'`不匹配，可以利用好后綴表跳轉至`"CDABE"`或`"DABE"`等位置繼續(xù)匹配。

（三）Boyer-Moore算法的優(yōu)勢與劣勢

優(yōu)勢：

1.高效率：在最好情況下，時間復雜度可達O(n/m)，遠優(yōu)于KMP算法。

2.適用于長模式串：當模式串長度m較大時，Boyer-Moore算法的效率優(yōu)勢明顯。

劣勢：

1.實現(xiàn)復雜：壞字符規(guī)則和好后綴規(guī)則的實現(xiàn)較為復雜，需要額外的空間存儲壞字符表和好后綴表。

2.部分情況性能下降：當主串和模式串匹配度較高時，壞字符規(guī)則和好后綴規(guī)則的跳轉效果可能不明顯。

五、總結

字符串匹配算法的選擇取決于實際應用場景和需求：

1.樸素匹配：

-適用場景：模式串較短，主串中重復子串較少，對效率要求不高。

-實現(xiàn)方式：簡單直觀，通過兩層循環(huán)逐字符比較。

-時間復雜度：O(nm)。

2.KMP算法：

-適用場景：模式串較長，主串中存在大量重復子串，需要多次匹配同一模式串。

-實現(xiàn)方式：通過構建Next數(shù)組，避免主串指針的無效回退。

-時間復雜度：O(n+m)。

3.Boyer-Moore算法：

-適用場景：模式串較長，對匹配效率要求極高。

-實現(xiàn)方式：通過壞字符規(guī)則和好后綴規(guī)則跳過無效比較。

-時間復雜度：O(n/m)（最好情況）。

在實際應用中，可以根據(jù)具體需求選擇合適的算法，或結合多種算法的優(yōu)點進行優(yōu)化。例如，對于長模式串且匹配次數(shù)較少的場景，Boyer-Moore算法可能更合適；而對于需要多次匹配同一模式串的場景，KMP算法的線性時間復雜度優(yōu)勢更為明顯。

一、引言

字符串匹配算法是計算機科學中常見的算法問題，其核心目標是在一個較長的文本串（主串）中查找是否存在一個較短的子串（模式串），并返回子串在主串中的起始位置。模式匹配原理涉及多種方法，包括樸素匹配、KMP算法、Boyer-Moore算法等。本文檔將重點介紹樸素匹配算法和KMP算法的基本原理、實現(xiàn)步驟及優(yōu)缺點分析。

二、樸素匹配算法（Brute-ForceAlgorithm）

樸素匹配算法是最直觀的字符串匹配方法，其基本思想是：從主串和模式串的第一個字符開始，依次比較兩個串的字符是否相同，若相同則繼續(xù)比較下一個字符，若不同則主串指針回退到上一個匹配位置的后一個字符，模式串指針回退到第一個字符，重新開始匹配。

（一）算法步驟

1.初始化：設置主串指針`i`從0開始，模式串指針`j`也從0開始。

2.匹配過程：

-比較`text[i]`和`pattern[j]`是否相同。

-若相同，`i`和`j`均加1，繼續(xù)比較下一個字符。

-若不同，`i`回退到`i-j+1`，`j`重置為0。

3.終止條件：

-若`j`達到模式串長度`m`，則匹配成功，返回`i-m`（匹配起始位置）。

-若`i`超過主串長度`n`仍未匹配成功，則匹配失敗，返回-1。

（二）示例

假設主串`text="ABCDABCDABE"`，模式串`pattern="ABCDABE"`：

1.初始：`i=0,j=0`，比較`'A'=='A'`，`i=1,j=1`，比較`'B'=='B'`，...

2.到`i=9,j=8`時，`'E'!='E'`，回退`i=5,j=0`，重新匹配。

3.最終匹配成功，起始位置為5。

（三）時間復雜度

-最好情況：O(n)，模式串第一個字符即匹配成功。

-最壞情況：O(nm)，模式串每個字符均需比較。

-平均情況：O(nm)。

三、KMP算法（Knuth-Morris-Pratt）

KMP算法是對樸素匹配的優(yōu)化，通過預處理模式串，避免主串指針的無效回退，從而將時間復雜度降低至O(n)。

（一）核心思想

KMP算法的核心是構建一個“部分匹配表”（Next數(shù)組），用于記錄模式串的前綴和后綴相同長度的最大值。當不匹配發(fā)生時，利用該表跳過已知的無效前綴，直接從有效位置繼續(xù)匹配。

（二）Next數(shù)組構建

Next數(shù)組的計算步驟如下：

1.初始化：`next[0]=-1`，`next[1]=0`。

2.從`i=2`開始，遍歷模式串：

-若`pattern[i-1]==pattern[next[i-1]]`，則`next[i]=next[i-1]+1`。

-否則，回退`k=next[next[i-1]]`，比較`pattern[i-1]==pattern[k]`，重復直到找到匹配或`k=-1`。

-若無匹配，`next[i]=0`。

示例：模式串`"ABCDABE"`的Next數(shù)組為`[-1,0,0,0,1,2,3]`。

（三）匹配過程

1.初始化：主串指針`i=0`，模式串指針`j=0`。

2.比較`text[i]`和`pattern[j]`：

-若相同，`i++,j++`。

-若`j==m`，匹配成功，返回`i-j`。

-若不匹配且`j>0`，更新`j=next[j]`（利用Next數(shù)組跳轉）。

-若`j==0`，`i++`繼續(xù)匹配。

3.匹配失敗返回-1。

（四）時間復雜度

-構建Next數(shù)組：O(m)。

-匹配過程：O(n)。

-總體時間復雜度：O(n+m)。

四、Boyer-Moore算法簡介

Boyer-Moore算法是另一種高效的模式匹配算法，其核心思想是通過“壞字符規(guī)則”和“好后綴規(guī)則”跳過大量無效比較，時間復雜度可達O(n/m)。

-壞字符規(guī)則：基于模式串中不匹配的字符，計算最大可跳轉距離。

-好后綴規(guī)則：基于模式串中匹配的后綴，計算最大可跳轉距離。

Boyer-Moore算法適用于長模式串，但實現(xiàn)相對復雜，此處不作詳細展開。

五、總結

字符串匹配算法的選擇取決于實際應用場景：

-樸素匹配：簡單易實現(xiàn)，適用于小規(guī)模數(shù)據(jù)。

-KMP算法：通用性強，效率高，適合大規(guī)模文本處理。

-Boyer-Moore算法：速度最快，但實現(xiàn)復雜，適用于長模式串。

三、KMP算法（Knuth-Morris-Pratt）

KMP算法是對樸素匹配的優(yōu)化，通過預處理模式串，避免主串指針的無效回退，從而將時間復雜度降低至O(n)。其核心在于利用模式串自身的特性，在發(fā)生不匹配時，盡可能多地跳過已經(jīng)確認不會匹配的部分，從而提高匹配效率。KMP算法主要由兩部分組成：部分匹配表的構建（Next數(shù)組的生成）和基于部分匹配表的匹配過程。

（一）核心思想與優(yōu)勢

KMP算法的核心思想是：當模式串與主串在某位置發(fā)生不匹配時，不需要將主串的指針回退到模式串指針之前的位置，而是利用已經(jīng)計算出的模式串的部分匹配信息，將模式串向后滑動，使其在主串中的某個位置與之前匹配成功的部分對齊，從而繼續(xù)比較。這種做法避免了主串指針的多次回退，顯著提高了算法的效率。

KMP算法的優(yōu)勢主要體現(xiàn)在以下方面：

1.時間效率高：在最好和平均情況下，時間復雜度為O(n)，遠優(yōu)于樸素匹配的O(nm)。

2.空間復雜度可控：Next數(shù)組的構建需要額外的空間，但其空間復雜度為O(m)，其中m是模式串的長度。

3.通用性強：適用于多種字符串匹配場景，特別是當模式串較長或主串中存在大量重復子串時，性能優(yōu)勢更為明顯。

（二）部分匹配表（Next數(shù)組）的構建

部分匹配表是KMP算法的關鍵，它記錄了模式串的前綴和后綴的最長相同子串的長度。通過該表，可以在不匹配發(fā)生時，確定模式串應該滑動的位置。部分匹配表的構建過程如下：

1.初始化：

-創(chuàng)建一個與模式串等長的數(shù)組`Next`，用于存儲部分匹配信息。

-初始化`Next[0]=-1`，因為單個字符的前綴和后綴不可能相同。

-設置指針`i`從1開始遍歷模式串，`k`為當前`i`的前一個位置的最長相同子串長度（即`Next[k]`）。

2.遍歷模式串，填充Next數(shù)組：

-對于每個位置`i`（從1到m-1），執(zhí)行以下步驟：

(1)比較當前字符與前綴的最長相同子串的最后一個字符：

-若`pattern[i-1]==pattern[k]`，則說明當前前綴和后綴的最長相同子串長度加1，即`Next[i]=k+1`，然后`i++`和`k++`繼續(xù)比較下一個字符。

-若不匹配，則需要更新`k`的值：將`k`設置為`Next[k-1]`，即回退到前一個最長相同子串的前一個位置，重復比較，直到`k==-1`或`pattern[i-1]==pattern[k]`。

(2)處理不匹配的情況：

-若`k==-1`，說明當前字符`pattern[i-1]`沒有前綴和后綴相同的情況，因此`Next[i]=0`，然后`i++`繼續(xù)遍歷。

(3)更新Next數(shù)組：

-每次比較后，若找到匹配，則`Next[i]=k+1`；若未找到，則`Next[i]=0`（當`k==-1`時）。

3.Next數(shù)組的含義：

-`Next[i]`表示模式串`pattern[0...i-1]`中，最長相等的前綴和后綴的長度。

-例如，模式串`"ABCDABE"`的Next數(shù)組為`[-1,0,0,0,1,2,3]`，表示：

-`pattern[0]`："A"→無前綴和后綴相同，`Next[0]=-1`。

-`pattern[0...1]`："AB"→無相同子串，`Next[1]=0`。

-`pattern[0...3]`："ABCD"→無相同子串，`Next[3]=0`。

-`pattern[0...4]`："ABCDAB"→"AB"=="AB"，`Next[4]=1`。

-`pattern[0...5]`："ABCDABE"→"AB"=="AB"，`Next[5]=2`。

-`pattern[0...6]`："ABCDABE"→"ABCD"=="ABCD"，`Next[6]=3`。

（三）基于部分匹配表的匹配過程

在構建完Next數(shù)組后，即可開始匹配過程。匹配過程中，主串指針`i`和模式串指針`j`分別從0開始遍歷，當字符匹配時，兩者同時后移；當不匹配時，利用Next數(shù)組確定模式串的滑動位置。具體步驟如下：

1.初始化：

-設置主串指針`i=0`，模式串指針`j=0`。

2.遍歷主串和模式串：

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

(1)若相同：

-`i++`，`j++`，繼續(xù)比較下一個字符。

-若`j==m`（模式串長度），則匹配成功，返回`i-j`（匹配起始位置）。

(2)若不同：

-若`j>0`，則將模式串指針`j`更新為`Next[j]`，即利用Next數(shù)組跳轉。

-若`j==0`，說明當前匹配失敗，僅移動主串指針`i++`，繼續(xù)匹配下一個位置。

3.匹配失?。?/p>

-若遍歷完主串仍未匹配成功（即`i==n`且未返回匹配位置），則返回-1表示不存在匹配。

4.示例：

-主串`text="ABCDABCDABE"`，模式串`pattern="ABCDABE"`，Next數(shù)組為`[-1,0,0,0,1,2,3]`。

-匹配過程：

-`i=0,j=0`，比較`'A'=='A'`，`i=1,j=1`。

-`i=2,j=2`，比較`'B'=='B'`，`i=3,j=3`。

-`i=4,j=4`，比較`'C'=='C'`，`i=5,j=5`。

-`i=6,j=6`，比較`'D'=='D'`，`i=7,j=7`。

-`i=8,j=8`，比較`'A'!='E'`，`j`更新為`Next[8]=3`（跳轉至`'CDABE'`）。

-`i=8,j=3`，比較`'A'=='A'`，`i=9,j=4`。

-`i=10,j=5`，比較`'B'=='B'`，`i=11,j=6`。

-`i=12,j=7`，比較`'E'=='E'`，`j==m`，匹配成功，返回`i-j=5`。

（四）時間復雜度分析

1.Next數(shù)組的構建：

-遍歷模式串一次，每次比較和更新Next數(shù)組的時間復雜度為O(1)，因此總時間復雜度為O(m)。

2.匹配過程：

-主串和模式串各遍歷一次，每次比較和指針更新操作的時間復雜度為O(1)，因此總時間復雜度為O(n)。

3.總體時間復雜度：

-O(m)+O(n)=O(n+m)，即線性時間復雜度。

（五）空間復雜度分析

-Next數(shù)組占用O(m)的額外空間，因此KMP算法的空間復雜度為O(m)。

（六）適用場景

KMP算法適用于以下場景：

1.模式串較長：當模式串長度m較大時，KMP算法的效率優(yōu)勢明顯。

2.主串中存在大量重復子串：KMP算法能夠有效利用重復子串的信息，減少不必要的比較。

3.需要多次匹配同一模式串：Next數(shù)組的預處理可以在多次匹配時復用，提高效率。

四、Boyer-Moore算法簡介

Boyer-Moore算法是另一種高效的字符串匹配算法，其核心思想是通過“壞字符規(guī)則”和“好后綴規(guī)則”跳過大量無效比較，時間復雜度可達O(n/m)。該算法在模式串較長時表現(xiàn)優(yōu)異，但實現(xiàn)相對復雜，因此此處僅作簡要介紹。

（一）壞字符規(guī)則（BadCharacterRule）

壞字符規(guī)則基于模式串中不匹配的字符，計算模式串可以滑動的最大距離。具體步驟如下：

1.壞字符表構建：

-創(chuàng)建一個壞字符表，記錄模式串中每個字符最后出現(xiàn)的位置。若字符未出現(xiàn)，則記錄為-1。

2.匹配過程中的壞字符處理：

-當主串和模式串在某位置不匹配時，找到模式串中與主串不匹配的字符（壞字符）。

-根據(jù)壞字符表，計算模式串可滑動的距離：

-