返回顶部

收藏

串的模式匹配

更多
#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] &amp;&amp; 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] &amp;&amp; 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 &amp;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",&amp;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;
}

标签:lua

收藏

0人收藏

支持

0

反对

0

发表评论