kmp算法中的next数组用c语言怎么求

KMP算法中的next数组可以用C语言实现，具体方法如下：

void getNext(char* p, int* next) {
    int i = 0, j = -1;
    next[0] = -1;

    while (p[i] != '\0') {
        if (j == -1 || p[i] == p[j]) {
            ++i;
            ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

其中，p是模式串，next是next数组。在函数中，i表示当前已匹配的前缀的下标，j表示当前已匹配的前缀的最长匹配后缀的下标。初始时，i=0，j=-1。

接下来进入一个while循环，循环条件是模式串p的下标不为'\0'。在循环中，如果j等于-1或者p[i]等于p[j]，则将i和j分别加1，并将next[i]赋值为j。如果p[i]不等于p[j]，则将j更新为next[j]，即找到p[0...j-1]的最长匹配后缀的下一个字符，继续与p[i]匹配。

最后，函数返回时，next数组中存储的就是模式串每个位置的最长匹配前缀的长度。

相关问题

kmp算法求next数组c语言

KMP算法是一种字符串匹配算法，用于在一个字符串中查找另一个字符串的出现位置。它的核心是求出模式串的next数组。下面是KMP算法求next数组的C语言代码实现：

void getNext(char* p, int* next) {
    int len = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < len - 1) {
        if (k == -1 || p[k] == p[j]) {
            ++k;
            ++j;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}

其中，p是模式串，next是next数组。这段代码中，我们首先将next[0]设置为-1。然后，我们通过循环计算next数组中的每个元素。在循环中，我们用k表示最长相等前后缀的长度，j表示后缀的索引。如果k==-1或者p[k]等于p[j]，我们将k和j都加1，并且将next[j]设置为k。否则，我们将k设置为next[k]（即p[0]~p[k-1]的最长相等前后缀的长度），继续循环。最后，我们得到了完整的next数组。

需要注意的是，这里的next数组的意义与其他地方可能不同，有些地方可能会将next[0]设置为0。这里我们将其设置为-1，是因为在KMP算法中，当next[j]==-1时，表示p[0]~p[j]中不存在任何一个前缀同时也是后缀。

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个字符前面最长的相同前缀后缀长度。