c中KMP算法中next数组跟主串有关系吗？

是的，KMP算法中的next数组与主串有关系。next数组用于记录模式串中每个位置处的最长公共前后缀长度，其中前后缀均不包括当前位置。因为每个位置的最长公共前后缀长度与前面的字符有关系，所以next数组的计算需要先确定主串的字符及其位置。

相关问题

KMP算法中的next数组C语言代码解析

KMP算法中的next数组是用来记录模式串中每个字符前面最长的相同前缀后缀长度的数组。下面是KMP算法中next数组的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数组详解

KMP算法是一种字符串匹配算法，用于在一个文本串S内查找一个模式串P的出现位置。其中，KMP算法的关键在于求解模式串P的next数组。下面详细介绍next数组的含义、求解方法以及应用。

1. 含义

next数组是一个长度为m（m为模式串P的长度）的数组，其中next[i]表示P[0:i]这个子串中，最长的既是其前缀又是其后缀的字符串的长度。特别地，next[0]=-1，next[1]=0。例如，当P="abab"时，其next数组为[-1,0,0,1]。

2. 求解

next数组的求解可以通过动态规划的方式实现。具体来说，在求解next[i]时，假设已知next[0:i-1]的值，我们需要找到一个最长的既是P[0:i-1]的前缀，也是P[1:i]的后缀的字符串。这个字符串可以通过比较P[0:j-1]和P[i-j:i-1]来得到，其中j=next[i-1]+1。

如果P[j]==P[i]，那么next[i]=j；否则，我们需要找到一个更短的字符串。此时，我们可以利用next数组的性质，从next[j]开始向前查找，直到找到一个P[k]等于P[i]为止，然后令next[i]=k。如果一直找到k=-1还没有找到，那么next[i]=0。

3. 应用

有了next数组之后，我们就可以利用KMP算法在文本串S中查找模式串P的出现位置。具体来说，我们维护两个指针i和j，分别指向S和P的当前位置。如果P[j]==S[i]，那么i和j都向后移动一位；否则，我们利用next数组来决定j的下一步移动位置。具体来说，如果next[j]=-1，或者next[j]<i，则令j=0，i不变；否则，令j=next[j]。这样，我们可以在O(n+m)的时间复杂度内完成匹配。