串的模式匹配算法

计算机上的非数值处理的对象基本上是字符串数据，在信息检索系统中，也是以字符串作为处理对象的。其中字符串的匹配操作广泛应用于建立词汇索引表等操作中，可见字符串的匹配操作在信息检索系统中是相当重要的。

子串的定位操作通常叫做串的模式匹配（其中T称为模式串），是各种串处理系统中的重要操作之一。严蔚敏版的《数据结构》教材上介绍了3种方式用于实现串的模式匹配（详细描述见课本P72，P79-P84），现简单介绍如下：

1.利用判等、求串长和求子串等操作来实现

基本思想：在主S中取从第i（i的初值为pos）个字符起、长度和串T相等的子串和串T比较，若相等，则求得函数值为i，否则i值增1直至串S中不存在和串T相等的子集为止。

int Index (String S, String T, int pos) {

 // T为非空串。若主串S中第pos个字符之后存在与 T相等的子串，

 //则返回第一个这样的子串在S中的位置，否则返回0

  if (pos > 0) {

    n = StrLength(S);  m = StrLength(T);  i = pos;

    while ( i <= n-m+1) {

        SubString (sub, S, i, m);

        if (StrCompare(sub,T) != 0)   ++i ;

        else return i ;

    } // while

  } // if

  return 0;          // S中不存在与T相等的子串

} // Index

 

2.简单的匹配算法

int Index(SString S, SString T, int pos) {

       // 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。

      // 其中，T非空，1≤pos≤StrLength(S)。

    i = pos;   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;

 } // Index

 

3.KMP匹配算法

 int Index_KMP(SString S, SString T, int pos) {

     // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的

     //KMP算法。其中，T非空，1≤pos≤StrLength(S)。

     i = pos;   j = 1;

     while (i <= S[0] && j <= T[0]) {

         if (j = 0 || S[i] == T[j]) { ++i;  ++j; }

                                               // 继续比较后继字符

         else  j = next[j];                       // 模式串向右移动

     }//while

    if (j > T[0])  return  i-T[0];                 // 匹配成功

    else return 0;

} // Index_KMP

********************************************************

void get_next(SString &T, int &next[] ) {

   // 求模式串T的next函数值并存入数组next。

   i = 1;   next[1] = 0;   j = 0;

    while (i < T[0]) {

        if (j == 0 || T[i] == T[j])

             {++i;  ++j; next[i] = j; }

        else  j = next[j];

    }

} // get_next

*********************************************************

   void get_nextval(SString &T, int &nextval[]) {

       //求模式串T的next函数修正值并存入数组nextval。

      i = 1;   nextval[1] = 0;   j = 0;

      while (i < T[0]) {

          if (j == 0 || T[i] == T[j]) {

              ++i;  ++j;

              if (T[i] != T[j])  nextval[i] = j;

              else  nextval[i] = nextval[j];

         }

        else  j = nextval[j];

     }

  } // get_nextval

 

 

 

 

 

 

 

 

 

 

 

 

 

程序清单：

1.简单匹配程序 SimpleMatch.c

#include <stdio.h>

#include <string.h> 

int index(char *s,char *t,int pos); 

int pos=0; 

 

void main() 

{ char s[80];  char t[20];   int n; 

  printf("please input the string of S:\n");

  gets(s);

  printf("please input the string of t:\n");

  gets(t);

 

  n=index(s,t,pos); 

  if(n!=0)

    printf("\n模式串 t 在主串 s 中第 %d 个位置之后。\n\n",n); 

  else

    printf("\n主串中不存在与模式串相匹配的子串!\n\n");

} 

 

int index(char *s,char *t,int pos){

 // 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。

 // 其中,T非空,1≤pos≤StrLen(S)。

 int i=pos,j=1; 

 

 while (i<=(int)strlen(s)&&j<=(int)strlen(t)) { 

  if (s[i]==t[j-1]) { ++ i; ++ j;}    //继续进行后续字符串的比较

  else {i=i-j+2;j=1; }            //指针后退重新开始匹配

 } 

 if (j>(int)strlen(t))  return i-strlen(t)+1; //匹配成功

 else //匹配不成功

 return 0; 

} //index

 

 

2.未修正next函数值的KMP匹配程序 KMP1.c

#include <stdio.h>

#include <string.h> 

int index_KMP(char *s,char *t,int pos); 

void get_next(char * t,int * next); 

 

int next[20]; 

int pos=0; 

 

void main() 

{ char s[80];  char t[20];   int n; 

  printf("please input the string of S:\n");

  gets(s);

  printf("please input the string of t:\n");

  gets(t);

 

  get_next(t,next); 

  n=index_KMP(s,t,pos); 

  if(n!=0)

   printf("\n模式串 t 在主串 s 中第 %d 个位置之后。\n\n",n); 

  else

   printf("\n主串中不存在与模式串相匹配的子串!\n\n");

} 

 

int index_KMP(char *s,char *t,int pos) 

//利用模式串的T的NEXT函数求t在主串s中的第pos个位置之后的位置的KMP算法。

//其中，t非空，1<=pos<=Strlength(s)。

{ 

 int i=pos,j=1; 

 while (i<=(int)strlen(s)&&j<=(int)strlen(t)) 

{ 

  if (j==0||s[i]==t[j-1]) //继续进行后续字符串的比较

  { 

   i++; 

   j++; 

  } 

  else j=next[j];      //模式串向右移动

 } 

 if (j>(int)strlen(t)) //匹配成功

 return i-strlen(t)+1; 

 else                  //匹配不成功

 return 0; 

} 

 

void get_next(char *t,int *next) 

//求模式串t的next函数的并存入数组next[]中。

{ 

 int i=1,j=0; 

 next[0]=next[1]=0; 

 while (i<(int)strlen(t)) 

 { 

  if (j==0||t[i]==t[j]) 

   { 

    i++; 

    j++; 

    next[i]=j; 

   } 

  else j=next[j]; 

 } 

}//get_next

 

 

3.修正next函数值后的KMP匹配程序 KMP2.c

#include <stdio.h>

#include <string.h> 

int index_KMP(char *s,char *t,int pos); 

void get_nextval(char * t,int * nextval); 

 

int nextval[20]; 

int pos=0; 

 

void main() 

{ char s[80];  char t[20];   int n; 

  printf("please input the string of S:\n");

  gets(s);

  printf("please input the string of t:\n");

  gets(t);

 

  get_nextval(t,nextval); 

  n=index_KMP(s,t,pos); 

  if(n!=0)

   printf("\n模式串 t 在主串 s 中第 %d 个位置之后。\n\n",n); 

  else

   printf("\n主串中不存在与模式串相匹配的子串!\n\n");

} 

 

int index_KMP(char *s,char *t,int pos) 

//利用模式串的T的NEXTVAl函数求t在主串s中的第pos个位置之后的位置的KMP算法。

//其中，t非空，1<=pos<=Strlength(s)。

{ 

 int i=pos,j=1; 

 while (i<=(int)strlen(s)&&j<=(int)strlen(t)) 

{ 

  if (j==0||s[i]==t[j-1]) //继续进行后续字符串的比较

  { 

   i++; 

   j++; 

  } 

  else j=nextval[j];      //模式串向右移动

 } 

 if (j>(int)strlen(t)) //匹配成功

 return i-strlen(t)+1; 

 else                  //匹配不成功

 return 0; 

} 

 

void get_nextval(char *t,int *nextval) 

//求模式串t的next函数修正值并存入数组nextval[]中。

{ 

 int i=1,j=0; 

 nextval[0]=nextval[1]=0; 

 while (i<(int)strlen(t)) 

 { 

  if (j==0||t[i]==t[j]) 

   { 

    ++i; 

    ++j; 

 

if(t[i]!=t[j])  nextval[i]=j;

else  nextval[i]=nextval[j];

   } 

  else j=nextval[j]; 

 } 

}//get_nextval

 

 

4.文件中字符匹配程序FileKMP.c

采用未修正next函数值的KMP算法

#include <stdio.h>

#include <string.h> 

int index_KMP(char *s,char *t,int pos); 

void get_next(char * t,int * next); 

int exit();

int next[5]; 

int pos=0; 

 

void main() 

{ char s[1000];  char t[20];   int n; 

  FILE *fp; 

  if((fp=fopen("d:wenjian.txt","rt"))==NULL)

  { printf("\nCannot open file strike any key exit!\n"); 

    exit(0); 

  }

  printf("The string S in the file is:\n");

  fputs(fgets(s,1000,fp),stdout);

  printf("\nPlease input the string of t:\n");

  gets(t);

 

  get_next(t,next); 

  n=index_KMP(s,t,pos); 

  if(n!=0)

  printf("\n模式串 t 在主串 s 中第 %d 个位置之后。\n\n",n); 

  else

  printf("\n主串中不存在与模式串相匹配的子串!\n\n");

} 

 

int index_KMP(char *s,char *t,int pos) 

//利用模式串的T的NEXT函数求t在主串s中的第pos个位置之后的位置的KMP算法。

//其中，t非空，1<=pos<=Strlength(s)。

{ 

 int i=pos,j=1; 

 while (i<=(int)strlen(s)&&j<=(int)strlen(t)) 

{ 

  if (j==0||s[i]==t[j-1]) //继续进行后续字符串的比较

  { 

   i++; 

   j++; 

  } 

  else j=next[j]; //模式串向右移动

 } 

 if (j>(int)strlen(t)) //匹配成功

 return i-strlen(t)+1; 

 else //匹配不成功

 return 0; 

} 

 

void get_next(char *t,int *next) 

//求模式串t的next函数的并存入数组next[]中。

{ 

 int i=1,j=0; 

 next[0]=next[1]=0; 

 while (i<(int)strlen(t)) 

 { 

  if (j==0||t[i]==t[j]) 

   { 

    i++; 

    j++; 

    next[i]=j; 

   } 

  else j=next[j]; 

} 

}//get_next

 

实验结果

1.程序1、2、3的结果均如下：

http://s15/bmiddle/7155aa134a5d011be390e&690

2.程序4的结果如下：

http://s11/bmiddle/7155aa134a5d01648b9da&690

 

 

http://s5/bmiddle/7155aa134a5d01b084084&690

 

 

http://s13/bmiddle/7155aa134a5d01a41dfcc&690

 

结果分析

    实验结果与在Word中进行字符统计的结果实质上是一致的。每个英文字母、英文标点或空格为1个字符长度，每个汉字和中文标点均占用2个字符长度，在汉语文档中，每个空格(即敲一次空格键）占有1个字符长度。如在“千古”之前有14个汉字，4个中文标点，1个空格，在“千古”之前有37个字符，故模式串在主串的第38个位置之后。