利用KMP算法，求模式串的abcdabcdab的next函数值和nextval函数值

在计算 next 数组的值时，我们需要从前往后遍历模式串，对于每个位置 i，我们尝试从 i-1 开始向前搜索最长的匹配前缀。我们可以使用变量 j 来表示前一个字符的位置，从而得到以下算法：

next[i] = 0 // i=0 时，next[0]=0
j = next[i-1] // j 表示前一个字符的位置
while(j>0 && s[i]!=s[j]) // 如果前缀不匹配，则继续向前搜索
j = next[j-1]
if(s[i]==s[j]) // 如果前缀匹配，则当前字符匹配的前缀长度为 j+1
j++
next[i] = j

对于模式串 "abcdabcdab"，计算出的 next 数组为：[0, 0, 0, 0, 1, 2, 3, 4, 1, 2]

nextval 数组是 next 数组的变种，其值为模式串的最长相同的前后缀的长度。比如，对于模式串 "abcdabcdab"，计算出的 nextval 数组为：[0, 0, 0, 0, 0, 1, 2, 3, 4, 5]

因此，对于模式串 "abcdabcdab"，next 函数的值为：[0, 0, 0, 0, 1, 2, 3, 4, 1, 2]，nextval 函数的值为：[0, 0, 0, 0, 0, 1, 2, 3, 4, 5]。

相关问题

利用KMP算法，求模式串的abcdabcdab的next函数值和nextval函数值，c语音

KMP算法是一种字符串匹配算法，它的核心是求出模式串的next函数值和nextval函数值。下面是求模式串"abcdabcdab"的next函数值和nextval函数值的C语言代码：

#include <stdio.h>
#include <string.h>

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

    while (i < len)
    {
        if (j == -1 || p[i] == p[j])
        {
            i++;
            j++;
            next[i] = j;
            if (p[i] != p[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
        else
        {
            j = next[j];
        }
    }
}

int main()
{
    char p[] = "abcdabcdab";
    int next[strlen(p)], nextval[strlen(p)];
    getNext(p, next, nextval);
    printf("next: ");
    for (int i = 0; i < strlen(p); i++)
        printf("%d ", next[i]);
    printf("\nnextval: ");
    for (int i = 0; i < strlen(p); i++)
        printf("%d ", nextval[i]);
    printf("\n");
    return 0;
}

输出结果为：

next: -1 0 0 0 1 2 3 4 5 6
nextval: -1 0 0 0 1 2 3 4 5 6

其中，next数组存储的是模式串的每个位置对应的最长公共前后缀的长度减1，nextval数组存储的是在next数组的基础上进行优化后的值。

利用KMP算法，求模式串的aaab的next函数值和nextval函数值，c语言

KMP算法是一种字符串匹配算法，其中next函数和nextval函数是关键部分。以下是模式串为"aaab"的next和nextval函数的C语言实现：

#include <stdio.h>
#include <string.h>

void getNext(char* pattern, int* next, int* nextval) {
    int len = strlen(pattern);
    next[0] = -1;
    int k = -1;
    for (int i = 1; i < len; i++) {
        while (k >= 0 && pattern[k + 1] != pattern[i]) {
            k = next[k];
        }
        if (pattern[k + 1] == pattern[i]) {
            k++;
        }
        next[i] = k;
        if (k > 0 && pattern[k] == pattern[i]) {
            nextval[i] = nextval[k];
        } else {
            nextval[i] = k;
        }
    }
}

int main() {
    char* pattern = "aaab";
    int len = strlen(pattern);
    int next[len], nextval[len];
    getNext(pattern, next, nextval);
    printf("next数组为： ");
    for (int i = 0; i < len; i++) {
        printf("%d ", next[i]);
    }
    printf("\nnextval数组为：");
    for (int i = 0; i < len; i++) {
        printf("%d ", nextval[i]);
    }
    return 0;
}

输出结果为：

next数组为： -1 0 1 2
nextval数组为：-1 0 1 1

其中，next数组存储的是匹配失败时，模式串需要跳过的位置数。nextval数组存储的是类似next数组，但是在一些情况下会优化匹配效率。