写一个c++next数组
时间: 2024-06-13 20:03:32 浏览: 4
C++中的`next`数组通常用于字符串匹配算法中,例如KMP算法。下面是一个简单的实现:
```c++
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> getNext(string pattern) {
int n = pattern.size();
vector<int> next(n, 0);
for (int i = 1, j = 0; i < n; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
if (pattern[i] == pattern[j]) {
j++;
}
next[i] = j;
}
return next;
}
int main() {
string pattern = "abababca";
vector<int> next = getNext(pattern);
for (int i = 0; i < next.size(); i++) {
cout << next[i] << " ";
}
cout << endl;
return 0;
}
```
`getNext`函数接受一个字符串`pattern`作为参数,返回一个`vector<int>`类型的`next`数组。在函数内部,我们使用了双指针的方法来计算`next`数组。具体来说,我们维护两个指针`i`和`j`,其中`i`表示当前位置,`j`表示前缀的末尾位置。如果`pattern[i]`和`pattern[j]`相等,那么`next[i]`就等于`j+1`;否则,我们需要将`j`向前移动,直到找到一个位置`k`,使得`pattern[k]`等于`pattern[i]`,或者`j`已经到达了字符串的开头。此时,`next[i]`就等于`next[k-1]+1`。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![xlsx](https://img-home.csdnimg.cn/images/20210720083732.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)