剪花布条皇星客栈

http://acm.hdu.edu.cn/showproblem.php?pid=2087
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     int length;    
 8     nextval[1]=0;
 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 nextval[ ])
30 {        
31     int i=1;
32     int j=1;
33     int count = 0;
34     while(i<=S[0]&&j<=T[0])    
35     {    
36         if( j==0 || S[i]==T[j] )    
37         {    
38             ++i;    
39             ++j;            //继续比较后继字符    
40         }    
41         else          
42             j=nextval[j];  //模式串向后移动    
43         if(j>T[0])
44         {
45             count++;    
46             j=1;
47         }        
48     }
49     return count;
50     
51 }
52 
53 int main( )
54 {    
55     char S[256],T[256];    
56     char *P,*Q;     
57     int nextval[256];    
58     while(1)    
59     {    
60         P=&S[1];    
61         Q=&T[1];    
62         scanf("%s",P);
63         if( S[1] == '#' )
64             break;
65         scanf("%s",Q);
66         S[0]=strlen(P);
67         T[0]=strlen(Q);  //得到两个字符串的长度    
68         get_nextval(T,nextval);
69         printf("%d\n",Index_KMP(S,T,nextval));
70         getchar( );
71     }    
72     return 0;      
73 }
剪花布条 皇星客栈

剪花布条皇星客栈
