KMP模式匹配算法示例weixin45720773的博客-

本来KMP算法的实现没几行代码，但是因为要满足题目要求的“显示每趟匹配过程”，而定义了很多花里胡哨的函数。

#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXLEN 255 typedef struct {  char ch[MAXLEN+1];  int length; }SString; int next[MAXLEN + 1]; int nextval[MAXLEN + 1]; int per[MAXLEN + 1] = { 0 }, total[MAXLEN + 1] = { 0 };//用来计算模式串各个字符参与匹配的次数 int main() {  void exam(SString father, SString son);      //检验主串和模式串是否正常  void menu();            //输出菜单栏  void BF(SString father, SString son, int K);    //BF算法  void KMP(SString father, SString son, int K);    //KMP算法  void KMPVAL(SString father, SString son, int K);   //KMP修正算法  SString father, son;  int K;//开始匹配的位置  int af, p;//p从串最后一个位置移动到串的第一个位置，af永远在p的后一位，用这两个变量来让ch[1]变成第一个元素，以此类推  int choose;//储存用户在菜单栏输入的选项  menu();  while (1) {   printf("请输入数字0—4来选择菜单项，其它输入则不起作用。nn");   scanf("%d", &choose);   if ((choose < 0) || (choose > 4)) {    printf("输入的数据无效！n");    exit(0);   }   printf("收到n");   switch (choose){    case 0:     printf("成功退出管理系统n");     exit(0);     break;    case 1:     printf("请依次输入主串、子串和匹配起始位置，中间用空格键隔开:n");     scanf("%s %s %d", father.ch, son.ch, &K);//输入字符串给father.ch和son.ch     father.length = strlen(father.ch);//计算主串长度并赋值给father.length     af = father.length;     /********************************/     for (p = af - 1; p >= 0;) {   /*主串字符向后串一位，      */      father.ch[af] = father.ch[p]; /*使得father.ch[i]成为主串的 */      af--; p--;      /*第i个元素      */     }         /********************************/     son.length = strlen(son.ch);//计算模式串长度并赋值给son.length     af = son.length;    /********************************/     for (p = af - 1; p >= 0;) {  /*模式串字符向后串一位，     */      son.ch[af] = son.ch[p];  /*使得son.ch[i]成为模式串的     */      af--; p--;     /*第i个元素      */     }        /********************************/      break;    case 2:     exam(father,son);     BF(father, son, K);     break;    case 3:     exam(father, son);     KMP(father, son, K);     break;    case 4:     exam(father, son);     KMPVAL(father,son,K);     break;    default:     break;   }  }  system("pause");  return 0; }   void exam(SString father, SString son) {  if (!father.ch && !father.length && !son.ch && !son.length) {   printf("输入的数据无效！n");//若主串或模式串中有数据没有成功输入，则退出程序   exit(0);  } }  void menu() {  printf("1．输入主串、子串和匹配起始位置n");  printf("2．朴素的模式匹配算法n");  printf("3．KMP改进算法(Next[])n");  printf("4．KMP改进算法(NextVal[])n");  printf("0．退出管理系统n");  } //输入一个存有字符串的结构体，输出该字符串并自动换行 void output(SString S) {  int i;  for (i = 1; i <= S.length; i++) {   putchar(S.ch[i]);  }  putchar('n'); }  //输出整型数组per[]，且只输出从per[1]到per[j]部分，并换行(一般用来输出各字符的匹配次数) void put_frequency(int per[],int j) {  int t;  for (t = 1; t <= j; t++)//输出模式串各字符在该次匹配中，参与匹配的次数。未输出的部分未匹配。  {   printf("%d", per[t]);   per[t] = 0;  }  putchar('n'); } //输出每一次匹配的过程 void process_compete(SString father,int i,SString son,int j,int len_comp) {  int t,blank;  void output(SString S);  output(father);  for (blank = i - 1 - len_comp; blank > 0; blank--)  {   putchar(' ');  }  for (t = 1; t <= j; t++)  {   putchar(son.ch[t]);  }          putchar('n'); }  void get_next(SString T, int next[]) {  int i,j;  i = 1;  j = 0;  next[0] = 1024;  next[1] = 0;  while (i<T.length) {   if (j == 0 || T.ch[i] == T.ch[j]){    i++; j++;    next[i] = j;   }   else {    j = next[j];   }  } } void get_nextval(SString T, int nextval[])  {    int i,j;   i = 1;   j = 0;   nextval[1] = 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];   }  } void BF(SString S, SString T, int K) {  //void output(SString S);//输入一个存有字符串的结构体，输出该字符串并自动换行  void process_compete(SString father, int i, SString son, int j, int len_comp);  void put_frequency(int per[], int j);  int i, j, result, num = 0;//i记录主串匹配的位置，j记录模式串匹配的位置，result存储匹配成功的位置，num存储匹配次数   //只需要i、j两个局部变量就可以实现BF算法，其余的变量只是为了展现模式匹配的过程   int len_comp = 0;//len_comp存储已经匹配成功的部分模式串长度  int blank;//blank存储需要空多少个空格字符  i = K; j = 1;  printf("-----------------------------------------------n");  while (i <= S.length && j <= T.length) {   //只要模式串中该位置参与了匹配，就记一次数，并在同一循环中输出、清空   per[j]++;   total[j] = total[j] + per[j];   printf("%d", per[j]);   per[j] = 0;    if (S.ch[i] == T.ch[j]) {    i++; j++;    len_comp++;   }   else {    num++;    printf("n第 %d 次匹配：n", num);//若n次匹配后成功，那么前n-1次匹配都是失败的    //output(S);    process_compete(S, i, T, j, len_comp);    printf("-----------------------------------------------n");    i = i - j + 2;    j = 1;    len_comp = 0;   }  }  printf("n第 %d 次匹配：n", ++num);  process_compete(S, i, T, j - 1, len_comp);  printf("-----------------------------------------------n");  if (j > T.length) {   result = i - T.length;   printf("n匹配成功，位置序号为：%dn", result);  }  else {   result = 0;   printf("匹配失败n");  }  printf("模式串总匹配次数：n");//无论是否成功匹配，都输出总的匹配次数  put_frequency(total, T.length);  printf("匹配总趟数：%dn", num); } void KMP(SString father, SString son, int K) {  //void output(SString S);//输入一个存有字符串的结构体，输出该字符串并自动换行  void get_next(SString T, int next[]);  void put_frequency(int per[], int j);  int i, j, result, num = 0;//i记录主串匹配的位置，j记录模式串匹配的位置，result存储匹配成功的位置，num存储匹配次数   //只需要i、j两个局部变量就可以实现BF算法，其余的变量只是为了展现模式匹配的过程   int len_comp = 0;//len_comp存储已经匹配成功的部分模式串长度  int blank;//blank存储需要空多少个空格字符  get_next(son, next);  {               //首先输出next[]各元素的数值   int pose_next;   printf("在KMP算法中，next数组是：n");   for (pose_next = 1; pose_next <= son.length; pose_next++) {    printf("%d", next[pose_next]);   }   putchar('n');  }  i = K;  j = 1;  printf("-----------------------------------------------n");  while (i <= father.length && j <= son.length) {   if (j) {    per[j]++;    total[j] = total[j] + per[j];   }   if (j == 0 || father.ch[i] == son.ch[j]) {    i++; j++;    len_comp++;   }   else {    num++;//若n次匹配后成功，那么前n-1次匹配都是失败的,    printf("第 %d 次匹配：n", num);//因此在循环体内只对匹配失败计数    put_frequency(per, j);    process_compete(father, i, son, j, len_comp);    len_comp = next[j] - 1;    j = next[j];    printf("-----------------------------------------------n");   }  }  printf("第 %d 次匹配：n", ++num);//最后一次匹配  put_frequency(per, j - 1);  process_compete(father, i, son, j - 1, len_comp);  printf("-----------------------------------------------n");  if (j > son.length) {   result = i - son.length;   //printf("第 %d 次匹配：n", ++num);//最后一次匹配成功   //output(father);   //for (blank = i - j; blank > 0; blank--)   // putchar(' ');   //output(son);   printf("匹配成功，位置序号为：%dn", result);   }  else {   result = 0;   printf("匹配失败n");  }  printf("总匹配次数：n");  put_frequency(total, son.length);  printf("匹配总趟数：%dn", num); } void KMPVAL(SString father, SString son, int K) {  //void output(SString S);//输入一个存有字符串的结构体，输出该字符串并自动换行  void get_nextval(SString T, int nextval[]);  void put_frequency(int per[], int j);  int i, j, result, num = 0;//i记录主串匹配的位置，j记录模式串匹配的位置，result存储匹配成功的位置，num存储匹配次数   //只需要i、j两个局部变量就可以实现BF算法，其余的变量只是为了展现模式匹配的过程   int len_comp = 0;//len_comp存储已经匹配成功的部分模式串长度  int blank;//blank存储需要空多少个空格字符  get_nextval(son, nextval);  {               //首先输出next[]各元素的数值   int pose_next;   printf("在KMPVAL算法中，nextval数组是：n");   for (pose_next = 1; pose_next <= son.length; pose_next++) {    printf("%d", nextval[pose_next]);   }   putchar('n');  }  i = K;  j = 1;  printf("-----------------------------------------------n");  while (i <= father.length && j <= son.length) {   if (j) {    per[j]++;    total[j] = total[j] + per[j];   }   if (j == 0 || father.ch[i] == son.ch[j]) {    i++; j++;    len_comp++;   }   else {    num++;       //若n次匹配后成功，那么前n-1次匹配都是失败的,    printf("第 %d 次匹配：n", num);//因此在循环体内只对匹配失败计数    put_frequency(per, j);    process_compete(father, i, son, j, len_comp);    len_comp = nextval[j] - 1;    j = nextval[j];    printf("-----------------------------------------------n");   }  }  printf("第 %d 次匹配：n", ++num);//最后一次匹配  put_frequency(per, j - 1);  process_compete(father, i, son, j - 1, len_comp);  printf("-----------------------------------------------n");  if (j > son.length) {   result = i - son.length;   printf("匹配成功，位置序号为：%dn", result);   }  else {   result = 0;   printf("匹配失败n");  }  printf("总匹配次数：n");  put_frequency(total, son.length);  printf("匹配总趟数：%dn", num); }