求模式串的失败函数next[j]
时间: 2024-06-05 20:08:34 浏览: 82
对于模式串的第j个字符,其对应的next[j]等于前缀字符串的后缀子串中最长的,既是前缀也是后缀的那一段的长度。即如果P[j]之前的字符串为S,那么next[j]表示S的最长相同前缀后缀的长度。通常表示为:
next[0] = -1, next[1] = 0;
设模式串P的长度为m(从0开始),则next数组的求法为:
for (int j = 2, k = 0; j <= m; j++) {
while (k != -1 && P[k + 1] != P[j]) {
k = next[k];
}
if (P[k + 1] == P[j]) {
k++;
}
next[j] = k;
}
其中“!= -1”是防止j退回到第一个字符,导致死循环。
相关问题
求模式串的失败函数next[j]代码
对不起,作为 AI 的我没有能力直接查找您所要求的代码。但是,您可以在网上搜索KMP算法中求模式串的失败函数next[j]代码,或者参考以下示例代码:
```
void getNext(char* pattern, int* next) {
int j = 0, k = -1;
int patternLen = strlen(pattern);
next[0] = -1;
while (j < patternLen) {
if (k == -1 || pattern[j] == pattern[k]) {
j++;
k++;
next[j] = k;
}
else {
k = next[k];
}
}
}
```
需要注意的是,这只是一个示例,具体实现可能会因人而异。
kmp算法 失败函数
kmp算法中的失败函数(也称为失效函数)用于在模式串中寻找最长的既是真前缀又是后缀的子串。失效函数是一个整数数组,数组中的每个元素表示当前位置之前的最长公共前后缀的长度。在KMP算法中,通过使用失效函数,可以避免在匹配过程中重复比较已匹配的部分。
具体实现失效函数的代码如下:
```python
def getNext(p):
next = [-1] * len(p)
j = 0
k = -1
while j < len(p) - 1:
if k == -1 or p[j] == p[k]:
j = j + 1
k = k + 1
next[j] = k
else:
k = next[k]
return next
```