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

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

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

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

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

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

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


// 計算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)前位置之前的最長相同前綴后綴長度
} else {
j = next[j]; // 如果不相等，則回退到前一個最長相同前綴后綴長度
}
}
return next;
}


// KMP算法
int kmp(string text, string pattern) {
int n = text.size();
int m = pattern.size();
vector<int> next = getNext(pattern); // 計算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]; // 如果不相等，則回退到前一個最長相同前綴后綴長度
}
}
if (j == m) { // 如果模式串遍歷完畢，說明匹配成功
return i - j; // 返回匹配位置
} else { // 如果主串遍歷完畢，說明匹配失敗
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)的時間內(nèi)找到模式串在主串中的位置，而不需要進(jìn)行多余的比較。KMP算法是一種經(jīng)典的字符串匹配算法，值得學(xué)習(xí)和掌握。