求子串在母串中所有出现的位置皇星客栈

给定主串S和模式串T，求T串在S串中所有出现的位置，允许不同位置的T串有部分重叠。例如：S='abababab'，T='abab'，T在S中出现的总次数就是3次（包括1、3、5三个起点位置，虽然S[1..4]与S[3..6]有部分重叠，但这是允许的）。输入信息包括两行，第一行为S串，第二行为T串；按从小到大的顺序输出所有T串出现的位置。

样例：

输入：

输出：

abababab

abab

1 3 5

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              printf("%d ",i-T[0]);   
46              j=nextval[j]; //特别注意这个j的变化
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          gets(P);
63          gets(Q);
64          S[0]=strlen(P);
65          T[0]=strlen(Q);  //得到两个字符串的长度    
66          get_nextval(T,nextval);
67          Index_KMP(S,T,nextval);
68          getchar( );
69      }    
70      return 0;      
71  }

求子串在母串中所有出现的位置 皇星客栈

求子串在母串中所有出现的位置皇星客栈