C语言版KMP算法

对朴素匹配模式算法的改进：

==主串指针不回溯==，==只有模式串指针回溯==

我们来讲解如何实现求next数组的代码

//求next数组
void getNext(SString S,int *next){
    next[1] = 0;
    int i = 1,j = 0;
    while(i<S.length){
        if(j==0||S.ch[i]==S.ch[j]){
            next[++i] = ++j;
        }else{
            j = next[j];
        }
    }
}

kmp我给他起了另一个名字，叫做看门牌

求next数组，next数组的含义，是字符串的前后缀交集最长的长度加1.

我们需要观察出两点，第一点，比如next[6] = 4,那么next[7]最大只能为5，也就是next[6]+1。

第二点至关重要

$$如果P_{next[j]} ≠ P_j ，那么next[j+1]可能的次大值为next[next[j]]+1$$

我们求出next数组的关键就是根据此

递归求出next数组值

接下来是kmp的代码

//kmp代码
int KMP(SString S,SString T){
    int i=1,j=1;
    int next[T.length+1];
    getNext(T,next);
    while(i<=S.length&&j<=T.length){
        if(j==0||S.ch[i]==T.ch[j]){
            ++i;
            ++j;
        }else{
            j = next[j];
        }
    }
    if(j>T.length){
        return i-T.length;
    }else{
        return 0;
    }
}

开始判断 S.ch[i]==T.ch[j] ，如果相等 ，那么继续比较后续字符，如果不相等，模式串进行回溯，当跳出循环，即已经匹配完所有字符，如果j已经大于T的长度时说明成功，反之失败

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAXLEN 255

typedef struct{
    char ch[MAXLEN];
    int length;
}SString;

//输入字符串
void assign(SString *S){
    int i = 1;
    char x;
    scanf("%c",&x);
    while(x!='\n'){
        S->ch[i++] = x;
        scanf("%c",&x);
    }
    S->length = i-1;
}
//打印字符串
void print(SString S){
    for(int i=1;i<=S.length;i++){
        printf("%c",S.ch[i]);
    }
    printf("\n");
}
//求next数组
void getNext(SString S,int *next){
    next[1] = 0;
    int i = 1,j = 0;
    while(i<S.length){
        if(j==0||S.ch[i]==S.ch[j]){
            next[++i] = ++j;
        }else{
            j = next[j];
        }
    }
}
//kmp代码
int KMP(SString S,SString T){
    int i=1,j=1;
    int next[T.length+1];
    getNext(T,next);
    while(i<=S.length&&j<=T.length){
        if(j==0||S.ch[i]==T.ch[j]){
            ++i;
            ++j;
        }else{
            j = next[j];
        }
    }
    if(j>T.length){
        return i-T.length;
    }else{
        return 0;
    }
}
int main(){
    SString S,T;
    printf("请输入主串：\n");
    assign(&S);
    printf("请输入模式串：\n");
    assign(&T);
    printf("匹配到的位置:%d",KMP(S,T));
    return 0;
}