实现KMP算法,给出代码
时间: 2023-12-14 14:56:02 浏览: 25
以下是KMP算法的实现代码:
```c++
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void computeLPSArray(string pat, vector<int>& lps) {
int len = 0;
int i = 1;
lps[0] = 0;
while (i < pat.length()) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len-1];
} else {
lps[i] = 0;
i++;
}
}
}
}
void KMP(string pat, string txt) {
int M = pat.length();
int N = txt.length();
vector<int> lps(M);
computeLPSArray(pat, lps);
int i = 0;
int j = 0;
while (i < N) {
if (pat[j] == txt[i]) {
i++;
j++;
}
if (j == M) {
cout << "Pattern found at index " << i-j << endl;
j = lps[j-1];
} else if (i < N && pat[j] != txt[i]) {
if (j != 0) {
j = lps[j-1];
} else {
i++;
}
}
}
}
int main() {
string txt = "ABABDABACDABABCABAB";
string pat = "ABABCABAB";
KMP(pat, txt);
return 0;
}
```
该代码实现了KMP算法,其中`computeLPSArray()`函数用于计算最长公共前后缀数组,`KMP()`函数用于匹配字符串。