串的模式匹配

2015/12/17 52485

清华大佬耗费三个月吐血整理的几百G的资源，免费分享！....>>>

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#define max 100
typedef unsigned char SString[max+1];
  
//简单模式匹配
int Index(SString S, SString T, int pos) {
     
// 返回子串T在主串S中第pos个字符之后的位置。
// 若不存在，则函数值为0。
// 其中，T非空，1≤pos≤StrLength(S)。
  
int i = pos;
int j = 1;
     
while (i <= S[0] && j <= T[0]) {
      if (S[i] == T[j]) {  // 继续比较后继字符
         ++i;
         ++j;
      } else {  // 指针后退重新开始匹配
         i = i-j+2;
         j = 1;
      }     
   }
   if (j > T[0])
     return i-T[0];
   else
     return 0;
}
//计算它的next值
void get_next(SString T, int *next) { 
  int i=1;
  next[1]=0;
  int j=0;
  
  
  while (i<T[0]) {
    if(j==0 || T[i]== T[j]) {
        ++i; 
        ++j; 
        next[i] = j;
    }
  
    else
    j= next[j];   
      
  }
}
  
int Index_KMP(SString S, SString T, int pos,int next[]) { 
  
  // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的
  // KMP算法。其中，T非空，1≤pos≤StrLength(S)。
  
  int i = pos;
  int j = 1;
  
  while (i <= S[0] && j <= T[0]) {
    if (j == 0 || S[i] == T[j]) {  // 继续比较后继字符
      ++i;  ++j;
    } else j = next[j]; // 模式串向右移动
  }
  if (j > T[0])
  return  i-T[0];   // 匹配成功
  else
  return 0;
}
// Index_KMP
void StrAssign(SString &T,char s[])
{
       int i=0;
       T[0]=strlen(s);
       for(i=1;i<T[0]+1;i++)
       {
              T[i]=s[i-1];
       }
}
int main()
{
 printf("1．输入一个主串S\n2．输入一个模式串T\n3. 计算模式串T的next函数值，并按格式显示出next函数值\n4．实现简单模式匹配 \n5．实现KMP模式匹配\n6. 继续/否？（y/n?）\n");
         
int case;
SString S;//主串
SString T;//模式串
int next[255];//next[]值
         
       while(1)
       {
              printf("请输入1到6\n");
              scanf("%d",&case);
              if(case ==1)
              {
                     printf("请输入一个主串\n");
                     char Str[max];
                     scanf("%s",Str);
                     StrAssign(S,Str);
              }
              else if(case ==2)
              {
                     printf("请输入一个模式串\n");
                     char Str[max];
                     scanf("%s",Str);
                     StrAssign(T,Str);
              }
              else if(case ==3)
              {
                     int i;
                     get_next(T, next);
                     for(i=1;i<T[0]+1;i++)
                     {
                            printf("%5d",next[i]);
                            if(i==5)
                                   printf("\n");
                     }
              }
              else if(case ==4)
              {
                     int pos=1;
                     printf("%d",Index(S,T,pos));
                     printf("\n");
              }
              else if(case ==5)
              {
                     int pos=1;
                     printf("%d",Index_KMP(S,T,pos,next));
                     printf("\n");
              }
              else if(case ==6)
              {
                     exit(0);
              }
              else
              {
              printf("输入的字符非法\n");
              }
       }
       return 0;
}