串的模式匹配

2015/12/17 50585
#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;
}
代码片段
