C++的KMP算法求next数组的代码
时间: 2024-10-15 07:28:27 浏览: 5
KMP算法是一种字符串匹配算法,用于在一个较长的文本串中查找指定模式串。构建Next数组是这个算法的关键步骤之一,它通过预处理模式串来避免不必要的字符比较。下面是一个简单的C++代码示例来计算Next数组:
```cpp
#include <vector>
std::vector<int> get_next(const std::string &pattern) {
std::vector<int> next(pattern.size(), -1);
int j = -1;
for (int i = 1; i < pattern.length(); ++i) {
while (j >= 0 && pattern[i] != pattern[j + 1]) {
j = next[j];
}
if (pattern[i] == pattern[j + 1]) {
j++;
}
next[i] = j;
}
return next;
}
```
在这个函数里,我们初始化一个大小与模式串长度相同的数组next,然后从第二个字符开始遍历模式串,当当前字符与前缀匹配时,索引j更新;如果不匹配,则回溯到下一个位置。最后返回的next数组存储了模式串中每个字符的最长公共前后缀的长度。
相关问题
KMP算法的next数组代码实现
KMP算法(Knuth-Morris-Pratt 算法),用于解决字符串匹配问题,通过预处理模式串,避免了不必要的回溯操作。核心是构建了一个next数组,它记录了模式串中每个位置到失配字符的最远距离。下面是next数组的一个基本的C++代码实现:
```cpp
#include <vector>
void computeNext(std::string pattern, std::vector<int>& next) {
int j = -1; // last matched character's index
next = -1;
for (int i = 1; i < pattern.length(); ++i) {
while (j != -1 && pattern[j + 1] != pattern[i]) {
j = next[j];
}
if (pattern[j + 1] == pattern[i]) {
++j;
}
next[i] = j;
}
}
// 使用next数组在主字符串中查找模式
bool kmpSearch(const std::string& text, const std::string& pattern) {
std::vector<int> next(pattern.size());
computeNext(pattern, next);
int i = 0, j = 0;
while (i < text.length()) {
if (text[i] == pattern[j]) {
i++;
j++;
} else if (j != -1) {
j = next[j];
} else {
i++;
}
if (j == pattern.size()) {
return true; // pattern found
}
}
return false; // pattern not found
}
```
在这个实现中,`computeNext`函数计算next数组,然后`kmpSearch`函数利用next数组进行字符串匹配。
如何求字符串kmp算法的nextval数组c++代码
KMP算法(Knuth-Morris-Pratt)用于在文本串中查找模式串的位置,通过构建前缀表(即nextval数组),避免了许多不必要的比较。下面是C++中使用KMP算法计算nextval数组的简单步骤和代码:
```cpp
#include <vector>
#include <string>
std::vector<int> get_next(const std::string &pattern) {
int len = pattern.size();
std::vector<int> next(len, 0); // 初始化nextval数组
int j = -1;
for (int i = 1; i < len; ++i) {
while (j != -1 && pattern[i] != pattern[j + 1]) {
j = next[j];
}
if (pattern[i] == pattern[j + 1]) {
j++;
}
next[i] = j;
}
return next;
}
// 示例用法
int main() {
std::string text = "ABABDABACDABABC";
std::string pattern = "ABABC";
auto next = get_next(pattern);
// 使用nextval数组对text进行匹配...
// ...
return 0;
}
阅读全文