数据结构–KMP算法进一步优化(nextval)

在KMP算法中，nextval数组是对应于next数组的一个优化。nextval数组的作用是在匹配失败时，可以跳过一些不必要的字符比较，从而提高匹配的效率。

nextval数组的计算方式和next数组类似，但是在计算过程中引入了一个新的指针k。k指向的是当前位置的前缀的末尾位置，即pattern[k]是当前位置的前缀的最后一个字符。k的初始值为0。

与next数组不同的是，在计算nextval[i]时，如果pattern[i]与pattern[j]不相等，则需要根据next[j]的值来更新j和k的值。具体的更新规则如下：

• 如果next[j]为0，则将j和k都加1。
• 如果next[j]不为0，则将j更新为next[j]，而k保持不变。

然后，将j的值赋给nextval[i]。这样，nextval数组就得到了更新。

在匹配过程中，如果在位置i和j处的字符不匹配，那么根据nextval[j]的值，可以直接将j更新为nextval[j]，而无需再次比较pattern[i]和pattern[j]。这样可以跳过一些不必要的字符比较，提高匹配的效率。

代码一：

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

void getNextvalArray(const char* pattern, int* nextval) {
    int n = strlen(pattern);
    int j = 0;
    int k = -1;
    nextval[0] = -1;
    while (j < n - 1) {
        if (k == -1 || pattern[j] == pattern[k]) {
            j++;
            k++;
            if (pattern[j] != pattern[k]) {
                nextval[j] = k;
            } else {
                nextval[j] = nextval[k];
            }
        } else {
            k = nextval[k];
        }
    }
}

int main() {
    const char* pattern = "ababaca";
    int n = strlen(pattern);
    int* nextval = (int*)malloc(n * sizeof(int));
    getNextvalArray(pattern, nextval);
    printf("Nextval Array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", nextval[i]);
    }
    printf("\n");
    free(nextval);
    return 0;
}

代码二：

typedef struct
{
    char ch[15];
    int length;
}SString;
int next[15], nextval[15];

void Get_Nextval(SString T)
{
    nextval[1] = 0;
    int i = 1, j = 0;
    while (i <= T.length)
    {
        if (j == 0 || T.ch[i] == T.ch[j])
        {
            i++;
            j++;
            if (T.ch[i] != T.ch[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
        else
            j = nextval[j];
    }
}

已知next数组求nextval数组

void Get_Nextval(SString T)
{
    nextval[1] = 0;
    for (int i = 2; i <= T.length; i++)
    {
        if (T.ch[i] == T.ch[next[i]])
            nextval[i] = nextval[next[i]];
        else
            nextval[i] = next[i];
    }
}