C++中的字符串匹配：一種高效的算法

字符串匹配是指在一個(gè)較長(zhǎng)的字符串中查找一個(gè)較短的字符串的位置，這是一個(gè)常見(jiàn)的編程問(wèn)題，也是許多應(yīng)用程序的基礎(chǔ)，比如文本編輯器、搜索引擎、數(shù)據(jù)壓縮等。在本文中，我們將介紹一種在C++中進(jìn)行字符串匹配的高效算法，即KMP算法。

KMP算法是由Donald Knuth、Vaughan Pratt和James H. Morris于1977年提出的，它的全稱(chēng)是Knuth-Morris-Pratt算法。KMP算法的核心思想是利用已經(jīng)匹配過(guò)的部分字符串來(lái)避免重復(fù)比較，從而提高匹配效率。具體來(lái)說(shuō)，KMP算法使用一個(gè)輔助數(shù)組（稱(chēng)為next數(shù)組）來(lái)記錄每個(gè)位置之前的最長(zhǎng)相同前綴后綴長(zhǎng)度，這樣當(dāng)匹配失敗時(shí)，可以根據(jù)next數(shù)組的值來(lái)移動(dòng)模式串（較短的字符串），而不是從頭開(kāi)始比較。

KMP算法的實(shí)現(xiàn)步驟如下：

1. 首先，根據(jù)模式串計(jì)算出next數(shù)組，這可以通過(guò)一個(gè)循環(huán)來(lái)完成，時(shí)間復(fù)雜度為O(m)，其中m是模式串的長(zhǎng)度。
2. 然后，從左到右遍歷主串（較長(zhǎng)的字符串），用兩個(gè)指針i和j分別指向主串和模式串的當(dāng)前位置，初始時(shí)i和j都為0。
3. 如果主串和模式串的當(dāng)前字符相同，那么i和j都加一，繼續(xù)比較下一個(gè)字符。
4. 如果主串和模式串的當(dāng)前字符不同，那么根據(jù)next數(shù)組的值來(lái)移動(dòng)模式串，即令j=next[j]，如果j變?yōu)?1，那么i加一，j變?yōu)?，重新開(kāi)始比較。
5. 重復(fù)步驟3和4，直到主串或模式串遍歷完畢。
6. 如果模式串遍歷完畢，那么說(shuō)明匹配成功，返回i-j作為匹配位置；如果主串遍歷完畢，那么說(shuō)明匹配失敗，返回-1。

為了更好地理解KMP算法的過(guò)程，我們給出一個(gè)示例代碼：

#include <iostream>
#include <vector>
#include <string>
using namespace std;


// 計(jì)算next數(shù)組
vector<int> getNext(string pattern) {
int m = pattern.size();
vector<int> next(m, -1); // 初始化為-1
int i = 0, j = -1; // i表示后綴末尾位置，j表示前綴末尾位置
while (i < m - 1) {
if (j == -1 || pattern[i] == pattern[j]) { // 如果相等或者j已經(jīng)回退到-1
i++; // 后綴末尾位置后移一位
j++; // 前綴末尾位置后移一位
next[i] = j; // 記錄當(dāng)前位置之前的最長(zhǎng)相同前綴后綴長(zhǎng)度
} else {
j = next[j]; // 如果不相等，則回退到前一個(gè)最長(zhǎng)相同前綴后綴長(zhǎng)度
}
}
return next;
}


// KMP算法
int kmp(string text, string pattern) {
int n = text.size();
int m = pattern.size();
vector<int> next = getNext(pattern); // 計(jì)算next數(shù)組
int i = 0, j = 0; // i表示主串當(dāng)前位置，j表示模式串當(dāng)前位置
while (i < n && j < m) {
if (j == -1 || text[i] == pattern[j]) { // 如果相等或者j已經(jīng)回退到-1
i++; // 主串當(dāng)前位置后移一位
j++; // 模式串當(dāng)前位置后移一位
} else {
j = next[j]; // 如果不相等，則回退到前一個(gè)最長(zhǎng)相同前綴后綴長(zhǎng)度
}
}
if (j == m) { // 如果模式串遍歷完畢，說(shuō)明匹配成功
return i - j; // 返回匹配位置
} else { // 如果主串遍歷完畢，說(shuō)明匹配失敗
return -1; // 返回-1
}
}


int main() {
string text = "ababababca";
string pattern = "abababca";
int pos = kmp(text, pattern);
cout << "The position of pattern in text is: " << pos << endl;
return 0;
}

輸出結(jié)果為：

The position of pattern in text is: 2

可以看到，KMP算法可以在O(n+m)的時(shí)間內(nèi)找到模式串在主串中的位置，而不需要進(jìn)行多余的比較。KMP算法是一種經(jīng)典的字符串匹配算法，值得學(xué)習(xí)和掌握。