1 #include <iostream>  2 #include <stdio.h>  3 #include <string.h>  4 #include <stdlib.h>  5 using namespace std;  6   7 #define MAXSIZE 1000    //最大字符数  8   9 struct SqString{    //定义顺序串结构 10     char data[MAXSIZE]; 11     int length; 12 }; 13  14 void GetNext(SqString t,int next[])    //求出模式串t的next数组 15 { 16     int j,k; 17     j=0,k=-1;next[0] = -1; 18     while(j<t.length-1){ 19         if(k==-1 || t.data[j]==t.data[k]){ 20             j++,k++; 21             next[j] = k; 22         } 23         else 24             k = next[k]; 25     } 26 } 27  28 void GetNextval(SqString t,int nextval[])    //求出模式串t的valnext数组 29 { 30     int j,k; 31     j=0,k=-1;nextval[0]=-1; 32     while(j<t.length){ 33         if(k==-1 || t.data[j]==t.data[k]){ 34             j++;k++; 35             if(t.data[j]!=t.data[k]) 36                 nextval[j] = k; 37             else 38                 nextval[j] = nextval[k]; 39         } 40         else 41             k = nextval[k]; 42     } 43 } 44  45 void printNext(SqString t,int next[])    //输出next数组 46 { 47     int i=0; 48     while(i<t.length){    //分段输出，每段8个数据 49         int j=i; 50         printf("j\t"); 51         printf("%d\t",i++); 52         for(;i<t.length && i%8;i++){    //输出j 53             printf("%d\t",i); 54         } 55         printf("\n"); 56         printf("next[j]\t"); 57         i=j; 58         printf("%d\t",next[i++]); 59         for(;i<t.length && i%8;i++){    //输出next[j] 60             printf("%d\t",next[i]); 61         } 62         printf("\n\n");     63     } 64 } 65  66 void printNextval(SqString t,int nextval[])    //输出nextval数组 67 { 68     int i=0; 69     while(i<t.length){    //分段输出，每段7个数据 70         int j=i; 71         printf("j\t\t"); 72         printf("%d\t",i++); 73         for(;i<t.length && i%7;i++){    //输出j 74             printf("%d\t",i); 75         } 76         printf("\n"); 77         printf("nextval[j]\t"); 78         i=j; 79         printf("%d\t",nextval[i++]); 80         for(;i<t.length && i%7;i++){    //输出next[j] 81             printf("%d\t",nextval[i]); 82         } 83         printf("\n\n");     84     } 85 } 86  87 int KMPIndex1(SqString s,SqString t,int next[]) 88 { 89     int i=0,j=0; 90     while(i<s.length && j<t.length){ 91         if(j==-1 || s.data[i]==t.data[j]) 92             i++,j++; 93         else 94             j=next[j]; 95     } 96     if(j>=t.length) 97         return i-t.length; 98     else 99         return -1;100 }101 102 int KMPIndex2(SqString s,SqString t,int nextval[])103 {104     int i=0,j=0;105     while(i<s.length && j<t.length){106         if(j==-1 || s.data[i]==t.data[j])107             i++,j++;108         else109             j = nextval[j];110     }111     if(j>=t.length)112         return i-t.length;113     else114         return -1;115 }116 117 int Menu()    //操作菜单118 {119     int in;120     printf("[1] 输入目标串\n");121     printf("[2] 输入模式串\n");122     printf("[3] 输出模式串的next数组\n");123     printf("[4] 输出模式串的nextval数组\n");124     printf("[5] 使用next[]进行匹配\n");125     printf("[6] 使用nextval[]进行匹配\n");126     printf("[0] 按其他键退出\n");127     scanf("%d",&in);128     return in;129 }130 131 void Reply(SqString &s,SqString &t,int next[],int nextval[],int in)    //对菜单的选项进行应答132 {133     switch(in){134     case 1:    //输入目标串135         scanf("%s",s.data);136         s.length = strlen(s.data);137         break;138     case 2:    //输入模式串139         scanf("%s",t.data);140         t.length = strlen(t.data);141         GetNext(t,next);142         printf("next[]生成成功！\n");143         GetNextval(t,nextval);144         printf("nextval[]生成成功！\n\n");145         break;146     case 3:    //输出模式串的next数组147         if(next[0]==0){148             printf("您还没有输入模式串！\n\n");149             break;150         }151         printNext(t,next);152         break;153     case 4:    //输出模式串的nextval数组154         if(next[0]==0){155             printf("您还没有输入模式串！\n\n");156             break;157         }158         printNextval(t,nextval);159         break;160     case 5:    //使用next[]进行匹配161         if(s.data[0]==‘\0‘){162             printf("您还没有输入目标串！无法匹配！\n\n");163             break;164         }165         if(next[0]==0){166             printf("您还没有输入模式串！\n\n");167             break;168         }169         in = KMPIndex1(s,t,next);170         if(in==-1)171             printf("匹配失败！\n\n");172         else {173             printf("使用next数组匹配成功！匹配位置为：%d\n",in);174             printf("匹配情况如下：\n");175             printf("%s\n",s.data);176             while(in--)177                 printf(" ");178             printf("%s\n\n",t.data);179         }180         break;181     case 6:    //使用nextval[]进行匹配182         if(s.data[0]==‘\0‘){183             printf("您还没有输入目标串！无法匹配！\n\n");184             break;185         }186         if(next[0]==0){187             printf("您还没有输入模式串！\n\n");188             break;189         }190         in = KMPIndex2(s,t,nextval);191         if(in==-1)192             printf("匹配失败！\n\n");193         else {194             printf("使用nextval数组匹配成功！匹配位置为：%d\n",in);195             printf("匹配情况如下：\n");196             printf("%s\n",s.data);197             while(in--)198                 printf(" ");199             printf("%s\n\n",t.data);200         }201         break;202     default:203         exit(1);204     }205     system("pause");206     system("cls");207 }208 209 int main()210 {211     int next[MAXSIZE+1]={0},nextval[MAXSIZE+1]={0};212     SqString s={0},t={0};213     while(1){214         int in = Menu();215         Reply(s,t,next,nextval,in);216     }217     return 0;218 }