严慧敏数据结构kmp算法完整代码
时间: 2024-04-25 17:18:52 浏览: 9
KMP算法是一种字符串匹配算法,用于在一个主串中查找一个模式串的出现位置。下面是KMP算法的完整代码示例:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 构建next数组
void getNext(const string& pattern, vector<int>& next) {
int n = pattern.size();
next.resize(n);
next = -1;
int i = 0, j = -1;
while (i < n - 1) {
if (j == -1 || pattern[i] == pattern[j]) {
++i;
++j;
next[i] = j;
} else {
j = next[j];
}
}
}
// KMP算法
int kmp(const string& text, const string& pattern) {
int m = text.size();
int n = pattern.size();
vector<int> next;
getNext(pattern, next);
int i = 0, j = 0;
while (i < m && j < n) {
if (j == -1 || text[i] == pattern[j]) {
++i;
++j;
} else {
j = next[j];
}
}
if (j == n) {
return i - j; // 返回模式串在主串中的起始位置
}
return -1; // 模式串不在主串中出现
}
int main() {
string text = "ABCABCDABABCDABCDABDE";
string pattern = "ABCDABD";
int pos = kmp(text, pattern);
if (pos != -1) {
cout << "Pattern found at position: " << pos << endl;
} else {
cout << "Pattern not found." << endl;
}
return 0;
}
```