1 ////////////////////////////////////////////////////////// 2 // String.cpp 3 // 4 // author:Leetao 5 ////////////////////////////////////////////////////////// 6 // 简介： 7 //   串的应用（数组模拟）：KMP匹配算法 8 //////////////////////////////////////////////////////////  9 /**10 * 11 *12 * @author Leetao13 * @version 1.014 * @date 2014.11.26 15 */ 16 #include<stdio.h>17 #include<string.h>18 19 #define MAXSIZE 2020 int next[MAXSIZE];21  22 //求模式串t的next函数值并存入数组next中 23 void get_next(char t[],int next[]) 24 {25     int i=1,j=0;26      next[0]=0;27     28     while(i<strlen(t))29     {30         if(j==0||t[i-1]==t[j-1])31         {32             ++i;33             ++j;34             next[i-1]=j;35         }36         else j=next[j-1]; 37     }38 }39 40 //KMP算法 41 int Index_KMP(char s[],char t[],int pos)42 {43     //利用模式串t的next函数求t在主串s中第pos个字符后的位置 44     int i=pos-1,j=0;45     46     while(i<strlen(s)&&j<strlen(t))   47     {48         if(j==0||s[i]==s[j])   //  49         {50             ++i;51             ++j;52         }53         else j=next[j-1];          //模式串右移 54     }55     56     if(j>strlen(t)) return (i-strlen(t));   //匹配成功 57     else return 0;58 }59 60 int main()61 {62     char s[MAXSIZE],t[MAXSIZE];63     int i,j,n;64     65     printf("please the one string s:\n");66         gets(s);67     printf("please the other string t:\n");68         gets(t);    69     printf("please enter the starting position:\n");70         scanf("%d",&n);71     72      //get_next73       get_next(t,next);74       75     if(Index_KMP(s,t,n))76         {77             printf("匹配成功,起始位置为%d!\n",Index_KMP(s,t,n));78             79         }80     else printf("匹配失败！\n");81     82     return 0;83 }84