kmp算法next计算代码
时间: 2023-05-26 18:07:26 浏览: 62
以下是KMP算法中next数组的计算代码,其中s是匹配串,next数组是等长的数组,用于存储s中每个前缀的最长公共前后缀长度。
```cpp
void getNext(string s, int* next) {
int i = 0, j = -1;
next[0] = -1;
while (i < s.length()) {
if (j == -1 || s[i] == s[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}
```
这段代码中,i表示已匹配的前缀的末尾位置,j表示当前前缀的最长公共前后缀的长度。当i和j所对应的字符相同时,j和i都向右移动一位,且next[i]设置为j。当不相同时,j向右跳转到next[j]位置,继续和i的字符比较。
相关问题
kmp算法next函数计算代码
KMP算法中的next函数可以通过动态规划的方式计算得出,其代码如下:
```
void getNext(string pattern, vector<int>& next) {
int n = pattern.size();
next[0] = -1;
int j = -1;
for (int i = 1; i < n; i++) {
while (j >= 0 && pattern[j + 1] != pattern[i]) {
j = next[j];
}
if (pattern[j + 1] == pattern[i]) {
j++;
}
next[i] = j;
}
}
```
其中,`pattern`表示需要匹配的模式串,`next`是一个长度为`n`的数组,用来存储`pattern`中每个位置对应的最长前缀后缀公共部分的长度。
在计算`next`数组的过程中,我们用`j`表示当前已知的最长前缀后缀公共部分的长度,初始化为-1(因为不存在长度为0的前缀后缀公共部分),然后从第二个位置开始遍历模式串,依次计算出每个位置对应的`next`值。
对于当前位置`i`,我们不断地向前更新`j`,直到找到一个位置`j+1`使得`pattern[j+1]=pattern[i]`,即在当前已知的最长前缀后缀公共部分的基础上,能够扩展出一个新的字符与当前位置`i`匹配。此时,位置`i`对应的`next`值即为`j+1`。
如果无法找到这样的位置`j+1`,说明当前位置`i`对应的最长前缀后缀公共部分长度为0,此时将`next[i]`赋值为-1即可。
最终得到的`next`数组即为KMP算法中使用的next数组。
kmp算法next计算方法
KMP算法是一种字符串匹配算法,它的核心是利用已匹配的字符串前缀和后缀的信息,避免了暴力的回溯,提高了字符串匹配的效率。其中,计算next数组是KMP算法的关键步骤之一。
下面是KMP算法next数组的计算方法:
1. 初始化next[0]=-1, next[1]=0。
2. 令j=0,i=1,从i=2开始枚举。
3. 如果p[i-1]=p[j],那么next[i]=j+1,j=j+1。
4. 如果p[i-1]≠p[j],则令j=next[j],直到满足p[i-1]=p[j]或者j=-1的情况。
5. 如果j=-1,则next[i]=0,j=0。
6. 重复步骤3~5,直到i=n。
其中,p表示要匹配的字符串,n为字符串长度,next数组存储了每个位置的最长相同前缀和后缀的长度。在KMP算法中,当匹配失败时,通过next数组可以快速将模式串向右移动,避免了暴力的回溯,提高了匹配的效率。