KMP代码
时间: 2023-07-02 13:07:57 浏览: 70
以下是 KMP 算法的 C++ 代码实现:
```cpp
void kmp(string text, string pattern) {
int n = text.length();
int m = pattern.length();
// 构建 next 数组
vector<int> next(m + 1, 0);
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j];
}
if (pattern[i] == pattern[j]) {
j++;
}
next[i + 1] = j;
}
// 匹配过程
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && text[i] != pattern[j]) {
j = next[j];
}
if (text[i] == pattern[j]) {
j++;
}
if (j == m) {
cout << "Pattern found at position " << i - m + 1 << endl;
j = next[j];
}
}
}
```
其中,`text` 表示文本串,`pattern` 表示模式串。`next` 数组是 KMP 算法中的核心,用于记录模式串中每个位置之前最长的相同前缀后缀长度。算法的时间复杂度为 $O(n+m)$,其中 $n$ 和 $m$ 分别为文本串和模式串的长度。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)