串匹配

  1 /*******************************************************************************
  2 /* <PRE>
  3 /* 版权所有    : -
  4 /* 模块名      : 串
  5 /* 文件名      : string.cpp
  6 /* 功能描述    : 串的模式匹配
  7 /* 作者        : <xxx>
  8 /* 版本        : 1.0
  9 /* -----------------------------------------------------------------------------
 10 /* 备注        : -
 11 /* -----------------------------------------------------------------------------
 12 /* 修改记录    :
 13 /* 日 期        版本     修改人        修改内容
 14 /* 2011/01/01   1.0      <xxx>         创建
 15 /* </PRE>
 16 *******************************************************************************/
 17 #include <stdio.h>
 18 #include <stdlib.h>
 19 #include <string>
 20 
 21 /******************************************************************************
 22 /* 数据结构声明
 23 /******************************************************************************/
 24 /* 串的定长顺序存储表示 */
 25 #define MAXSTRLEN 255   /* 用户可以在255以内定义最大串长 */
 26 typedef unsigned char SString[MAXSTRLEN + 1];  /* 0号单元存放串的长度 */
 27 
 28 /******************************************************************************
 29 /* 函数原型声明
 30 /******************************************************************************/
 31 void get_next(SString T, int next[]);
 32 void get_nextval(SString T, int nextval[]);
 33 
 34 /*******************************************************************************
 35 /* <FUNC>
 36 /* 函数名   : Index
 37 /* 功能     : 求子串位置
 38 /* 参数     : -
 39 /* 返回值   : -
 40 /* 备注     : 返回子串T在主串S中第pos个字符之后的位置。若不存在, 则函数值为0
 41 /*            其中, T非空, 1 <= pos <= StrLength(S)
 42 /* 作者     : <xxx>
 43 /* </FUNC>
 44 *******************************************************************************/
 45 int Index(SString S, SString T, int pos) {
 46     int i = pos; int j = 1;
 47     while (i <= S[0] && j <= T[0]) {
 48         if (S[i] == T[j]) {++i;  ++j;} //继续比较后继字符
 49         else {i = i - j + 2;  j = 1;}  //指针后退重新开始匹配
 50     }
 51     if (j > T[0]) return i - T[0];
 52     else return 0;
 53 }
 54 
 55 /*******************************************************************************
 56 /* <FUNC>
 57 /* 函数名   : Index_KMP_1
 58 /* 功能     : 求子串位置的KMP算法1
 59 /* 参数     : -
 60 /* 返回值   : -
 61 /* 备注     : 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
 62 /*            其中, T非空, 1 <= pos <= StrLength(S)
 63 /* 作者     : <xxx>
 64 /* </FUNC>
 65 *******************************************************************************/
 66 int Index_KMP_1(SString S, SString T, int pos) {
 67     int i = pos; int j = 1;
 68     int *next = (int *)malloc((T[0] + 1) * sizeof(int));
 69     get_next(T, next);
 70     while (i <= S[0] && j <= T[0]) {
 71         if (j == 0 || S[i] == T[j]) {++i;  ++j;} //继续比较后继字符
 72         else j = next[j];                        //模式串向右移动
 73     }
 74     free(next);
 75     if (j > T[0]) return i - T[0];               //匹配成功
 76     else return 0;
 77 }
 78 
 79 /*******************************************************************************
 80 /* <FUNC>
 81 /* 函数名   : get_next
 82 /* 功能     : 求next函数值
 83 /* 参数     : -
 84 /* 返回值   : -
 85 /* 备注     : 求模式串T的next函数值, 并存入数组next
 86 /* 作者     : <xxx>
 87 /* </FUNC>
 88 *******************************************************************************/
 89 void get_next(SString T, int next[]) {
 90     int i = 1, j = 0;    next[1] = 0;
 91     while (i < T[0]) {
 92         if (j == 0 || T[i] == T[j]) {++i;  ++j; next[i] = j;}
 93         else j = next[j];
 94     }
 95 }
 96 
 97 /*******************************************************************************
 98 /* <FUNC>
 99 /* 函数名   : Index_KMP_2
100 /* 功能     : 求子串位置的KMP算法2
101 /* 参数     : -
102 /* 返回值   : -
103 /* 备注     : 利用模式串T的nextval函数求T在主串S中第pos个字符之后的位置的KMP算法
104 /*            其中, T非空, 1 <= pos <= StrLength(S)
105 /* 作者     : <xxx>
106 /* </FUNC>
107 *******************************************************************************/
108 int Index_KMP_2(SString S, SString T, int pos) {
109     int i = pos; int j = 1;
110     int *nextval = (int *)malloc((T[0] + 1) * sizeof(int));
111     get_nextval(T, nextval);
112     while (i <= S[0] && j <= T[0]) {
113         if (j == 0 || S[i] == T[j]) {++i;  ++j;}    //继续比较后继字符
114         else j = nextval[j];                        //模式串向右移动
115     }
116     free(nextval);
117     if (j > T[0]) return i - T[0];                  //匹配成功
118     else return 0;
119 }
120 
121 /*******************************************************************************
122 /* <FUNC>
123 /* 函数名   : get_nextval
124 /* 功能     : 求nextval函数值
125 /* 参数     : -
126 /* 返回值   : -
127 /* 备注     : 求模式串T的next函数值修正值并存入数组nextval
128 /* 作者     : <xxx>
129 /* </FUNC>
130 *******************************************************************************/
131 void get_nextval(SString T, int nextval[]) {
132     int i = 1;   nextval[1] = 0;  int j = 0;    
133     while (i < T[0]) {
134         if (j == 0 || T[i] == T[j]) {
135             ++i;  ++j; 
136             if (T[i] != T[j]) nextval[i] = j;
137             else nextval[i] = nextval[j];
138         }
139         else j = nextval[j];
140     }
141 }
142 
143 /*******************************************************************************
144 /* <FUNC>
145 /* 函数名   : main
146 /* 功能     : 测试函数
147 /* 参数     : -
148 /* 返回值   : -
149 /* 备注     : -
150 /* 作者     : <xxx>
151 /* </FUNC>
152 *******************************************************************************/
153 void main()
154 {
155     SString S, T;
156     S[0] = strlen("ababcabcacbab");
157     T[0] = strlen("abcac");
158     strcpy((char *)&S[1], "ababcabcacbab");
159     strcpy((char *)&T[1], "abcac");
160 
161     printf("Index: %d\n", Index(S, T, 1));
162     printf("Index_KMP_1: %d\n", Index_KMP_1(S, T, 1));
163     printf("Index_KMP_2: %d\n", Index_KMP_2(S, T, 1));
164 }