#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];
}
}
}
