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

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

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

KMP算法的實現步驟如下：

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

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

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


// 計算next數組
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已經回退到-1
i++; // 后綴末尾位置后移一位
j++; // 前綴末尾位置后移一位
next[i] = j; // 記錄當前位置之前的最長相同前綴后綴長度
} 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數組
int i = 0, j = 0; // i表示主串當前位置，j表示模式串當前位置
while (i < n && j < m) {
if (j == -1 || text[i] == pattern[j]) { // 如果相等或者j已經回退到-1
i++; // 主串當前位置后移一位
j++; // 模式串當前位置后移一位
} 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;
}

輸出結果為：

The position of pattern in text is: 2

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