- #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;
- }
- //该片段来自于http://www.codesnippet.cn/detail/1301201614429.html
来源: http://www.codesnippet.cn/detail/1301201614429.html