C语言数据结构-algo4-1.c

blake

1. /* algo4-1.c 实现算法4.6、4.7的程序 */
   
2. #include"c1.h"
   
3. #include"c4-1.h"
   
4. #include"bo4-1.c"
   
5. 
   
6. void get_next(SString T,int next[])
   
7. { /* 求模式串T的next函数值并存入数组next 算法 4.7 */
   
8.    int i=1,j=0;
   
9.    next[1]=0;
   
10.    while(i<T[0])
    
11.      if(j==0||T[i]==T[j])
    
12.      {
    
13.        ++i;
    
14.        ++j;
    
15.        next[i]=j;
    
16.      }
    
17.      else
    
18.        j=next[j];
    
19. }
    
20. 
    
21. int Index_KMP(SString S,SString T,int pos,int next[])
    
22. { /* 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。 */
    
23.    /* 其中,T非空,1≤pos≤StrLength(S)。算法 4.6 */
    
24.    int i=pos,j=1;
    
25.    while(i<=S[0]&&j<=T[0])
    
26.      if(j==0||S[i]==T[j]) /* 继续比较后继字符 */
    
27.      {
    
28.        ++i;
    
29.        ++j;
    
30.      }
    
31.      else /* 模式串向右移动 */
    
32.        j=next[j];
    
33.    if(j>T[0]) /* 匹配成功 */
    
34.      return i-T[0];
    
35.    else
    
36.      return 0;
    
37. }
    
38. 
    
39. void main()
    
40. {
    
41.    int i,j,*p;
    
42.    SString s1,s2; /* 以教科书中图4.5为例 */
    
43.    StrAssign(s1,"acabaabaabcacaabc");
    
44.    printf("主串为: ");
    
45.    StrPrint(s1);
    
46.    StrAssign(s2,"abaabcac");
    
47.    printf("子串为: ");
    
48.    StrPrint(s2);
    
49.    i=StrLength(s2);
    
50.    p=(int*)malloc((i+1)*sizeof(int)); /* 生成s2的next数组 */
    
51.    get_next(s2,p);
    
52.    printf("子串的next函数为: ");
    
53.    for(j=1;j<=i;j++)
    
54.      printf("%d ",*(p+j));
    
55.    printf("\n");
    
56.    i=Index_KMP(s1,s2,1,p);
    
57.    if(i)
    
58.      printf("主串和子串在第%d个字符处首次匹配\n",i);
    
59.    else
    
60.      printf("主串和子串匹配不成功\n");
    
61. }

复制代码