c中KMP算法中next数组跟主串有关系吗?
时间: 2023-06-10 20:03:42 浏览: 54
是的,KMP算法中的next数组与主串有关系。next数组用于记录模式串中每个位置处的最长公共前后缀长度,其中前后缀均不包括当前位置。因为每个位置的最长公共前后缀长度与前面的字符有关系,所以next数组的计算需要先确定主串的字符及其位置。
相关问题
KMP算法中的next数组C语言代码解析
KMP算法中的next数组是用来记录模式串中每个字符前面最长的相同前缀后缀长度的数组。下面是KMP算法中next数组的C语言代码解析:
```c
void getNext(char* p, int* next) {
int len = strlen(p);
int i = , j = -1;
next[] = -1;
while (i < len) {
if (j == -1 || p[i] == p[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}
```
该函数接受两个参数:模式串p和next数组。函数中的变量i和j分别表示当前匹配到的位置和最长相同前缀后缀的长度。变量len表示模式串的长度。next[]初始化为-1,表示模式串的第一个字符前面没有相同的前缀和后缀。
在while循环中,如果j等于-1或者p[i]等于p[j],则说明当前字符匹配成功,i和j都向后移动一位,并将next[i]赋值为j。如果当前字符匹配失败,则将j更新为next[j],即将j回溯到上一个最长相同前缀后缀的位置,继续匹配。
最终,函数返回next数组,其中next[i]表示模式串中第i个字符前面最长的相同前缀后缀长度。
kmp算法中的next数组用c语言怎么求
KMP算法中的next数组可以使用动态规划的思路,用C语言来求next数组的过程可以描述如下:
1. 将next数组的第一个元素设置为-1。
2. 从第二个元素开始,设置为其前一个元素的next值,也就是next[i] = next[i-1] + 1。
3. 如果下标i处的字符和下标next[i-1]处的字符相同,则next[i] = next[i-1] + 1;
4. 如果下标i处的字符和下标next[i-1]处的字符不同,则找到下一个最大相同前缀后缀的位置,将next[i]设置为该位置的next值。
5. 重复上述步骤,直到数组的最后一个元素。