数据结构严蔚敏书上的改进，修正最后的KMP 皇星客栈

View Code
 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 void get_nextval(char T[ ],int nextval[ ])
 5 {//求模式串Ｔ的next函数修正值并存入数组nextval.    
 6     int i=1,j=0;
 7     nextval[1]=0;
 8     int length;
 9     length=strlen(T);
10     
11     while(i<length)
12     {    
13         if(j==0||T[i]==T[j])
14         {
15             ++i;
16             ++j;
17             if(T[i]==T[j]) 
18                 nextval[i]=nextval[j];
19             else 
20                 nextval[i]=j;
21         }    
22         else        
23             j=nextval[j];        
24     }    
25 }
26 
27 
28 
29 int Index_KMP(char S[ ],char T[ ],int pos,int nextval[ ])
30 {
31     //利用模式串Ｔ的nextval函数求Ｓ在主串Ｔ的第pos个字符之后的位置的    
32     //KMP算法。其中，Ｓ非空，1<=pos<=lengthT;
33     int i=pos;    
34     int j=1;
35     while(i<=S[0]&&j<=T[0])    
36     {    
37         if( j==0 || S[i]==T[j] )    
38         {    
39             ++i;    
40             ++j;            //继续比较后继字符    
41         }    
42         else          
43             j=nextval[j];  //模式串向后移动    
44     }
45     if(j>T[0])    
46         return (i-T[0]);//匹配成功
47     else     
48         return 0;    
49 }
50 
51 int main( )
52 {    
53     char S[256],T[256];    
54     char *P,*Q;     
55     int nextval[256];    
56     int pos;  //指定在主串S中开始比较的位置    
57     while(1)    
58     {    
59         P=&S[1];    
60         Q=&T[1];    
61         gets(P);    
62         gets(Q);          //输入两个字符串    
63         S[0]=strlen(P);
64         T[0]=strlen(Q);  //得到两个字符串的长度    
65         scanf("%d",&pos);
66         get_nextval(T,nextval);
67         printf("%d\n",Index_KMP(S,T,pos,nextval));
68         getchar( );
69     }    
70     return 0;      
71 }