KMP算法

next数组

next[j]=k：k是当模式串中第j个字符与主串中相应字符 “失配”时，在模式串中需重新和主串中该字符进行比较的字符的位置。

$$
\left.{next[j]=}\left{\begin{array}{ll}
\mathbf{0} & \text{当 j=1 时(代表下一趟比较}\mathrm{i=i+1,j=1})\\
\mathbf{max{k\mid1<k<j}\text{且前k - 1个元素和后k-1个元素一致}}&\text{此集合不为空时,下一趟比较i = i ,j = k}\\
\mathbf{1}&\text{其它情況(即$j \ne 1且上述集合为空$)}\end{array}\right.\right.
$$

快速填写记法：

（1）字符串从1开始标号；

（2）next[1]默认为0；

（3）next[i] = 前 i -1 位字符串公共前后缀的长度 + 1；

Notice：

前缀：除最后一个字符外，一个字符串的全部头部组合；

后缀：除第一个字符外，一个字符串全部的尾部组合；所以，"aaa"的公共前缀和长度为2。

void GetNext(const char *T, int *next) {
    int j = 1, k = 0; // j 表示模式串位置, k 是前缀长度
    next[1] = 0;      // 初始化 next 数组
    while (j < strlen(T)) {
        if (k == 0 || T[j] == T[k]) {
            j++;
            k++;
            next[j] = k; // 更新 next[j]
        } else {
            k = next[k]; // 回退
        }
    }
}

nextval数组

引入原因：next数组中，前后两个相邻的字母如果相同，在匹配过程中遇到需要回退的情况，可以跳过回退到该字母。

$$
\begin{array}{l}
nextval[i] & = 1\
nextval[i] & = \left{\begin{array}{ll}
nextval[i] = nextval[next[i]] & \text{当$Pattern_i = Pattern_{next[i]}$时}\\
nextval[i] = next[i] & \text{当$Pattern_i \ne Pattern_{next[i]}$时}\end{array}\right.
\end{array}
$$

完整代码

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

void GetNextVal(const char *T, int *nextval) {
    int j = 1, k = 0; // j 表示模式串位置, k 是前缀长度
    nextval[1] = 0;   // 初始化 nextval 数组
    
    while (j < strlen(T)) {
        if (k == 0 || T[j] == T[k]) {
            j++;
            k++;
            if (T[j] != T[k]) {
                nextval[j] = k; // 当 T[j] ≠ T[next[j]] 时，直接赋值
            } else {
                nextval[j] = nextval[k]; // 当 T[j] == T[next[j]] 时，优化跳跃
            }
        } else {
            k = nextval[k]; // 回退
        }
    }
}

int Index_KMP(const char *S, const char *T, int pos) {
    int nextval[100]; // 假设模式串长度不超过 100
    GetNextVal(T, nextval); // 生成 nextval 数组
    
    int i = pos; // 主串的当前指针
    int j = 1;   // 模式串的当前指针
    
    printf("i\tj\n");
    while (i <= strlen(S) && j <= strlen(T)) {
        printf("%d\t%d\n", i, j); // 输出当前的 i 和 j 值
        
        if (j == 0 || S[i - 1] == T[j - 1]) {
            i++;
            j++;
        } else {
            j = nextval[j]; // 模式串向右移动
        }
    }
    
    if (j > strlen(T)) {
        return i - strlen(T); // 匹配成功，返回匹配位置
    } else {
        return 0; // 匹配失败
    }
}

int main() {
    const char S[] = "abcaacabcab"; // 主串
    const char T[] = "abcab";       // 模式串
    
    printf("主串: %s\n", S);
    printf("模式串: %s\n", T);
    printf("匹配过程:\n");
    
    int pos = Index_KMP(S, T, 1); // 从第一个字符开始匹配
    
    if (pos > 0) {
        printf("匹配成功，位置: %d\n", pos);
    } else {
        printf("匹配失败\n");
    }
    return 0;
}