KMP算法及其实现

• 首先推荐一个博客，讲的十分细致易懂
  从头到尾彻底理解KMP
• 代码实现

#include <stdio.h>
#include <stdlib.h>
#define MAX 10000

typedef struct string{
    char ch[MAX];
    int len;
}string;

int size(string *s);
int KMP(string *l1,string *l2,int next[]);
void getNext(string *l,int next[]);

int main(int argc, const char * argv[]) {
    string *l1 = (string *)malloc(sizeof(string));
    string *l2 = (string *)malloc(sizeof(string));
    printf("输入待匹配的字符串：");
    scanf("%s",l1->ch);size(l1);
    printf("输入模式字符串：");
    scanf("%s",l2->ch);size(l2);
    int next[MAX];
    getNext(l2, next);
    if (KMP(l1, l2, next)) {
        printf("匹配成功\n");
    }else
        printf("匹配失败\n");
    return 0;
}

int size(string *s){
    int i=0;
    while (s->ch[i] != '\0') {
        i++;
    }
    s->len = i;
    return s->len;
}

int KMP(string *l1,string *l2,int next[]){
    int i=0,j=0;
    while (i<l1->len && j<l2->len) {
        if (j == -1 || l1->ch[i] == l2->ch[j]) {
            i++;
            j++;
        }else{
            j = next[j];
        }
    }
    if (j==l2->len) {
        return 1;
    }else
        return 0;
}

void getNext(string *l,int next[]){
    int i=0,k=-1;   //k表示前缀，i表示后缀
    next[0]=-1;
    while (i<l->len-1) {
        if (k == -1 || l->ch[k] == l->ch[i]) {
            ++k;
            ++i;
            if (l->ch[k] != l->ch[i]) {
                next[i] = k;
            }else{
                next[i] = next[k];
            }
        }else{
            k = next[k];
        }
    }
}