字符串的模式匹配是一个比较经典的问题：假设有一个字符串S，称其为主串，然后还有一个字符串T，称其为子串。

现在要做的是，从主串S当中查找子串T的位置，如果存在返回位置值，如果不存在返回-1。另外主串又称为目标串，

子串称为模式串。

 

暴力匹配算法

这是一个经典的串匹配问题，涉及的算法也比较多，先讨论第一种简单的暴力算法，思路如下

将主串S的第pos个字符 与 子串T的第一个字符比较， 若相同，继续比较子串和主串后面的字符。

若不相同，那么从主串S的第(pos + 1)个字符开始继续向后匹配，直到匹配到主串的(S.len - T.len)的位置为止

匹配成功返回索引值，匹配失败返回-1，下面是实现代码

#include 
      
       #include 
       
        #define OK 1typedef int Status;typedef struct {  char *data;  int  len;}String;Status initString(String *T){  T->data = NULL;  T->len  = 0;  return OK;}Status strAssign(String *T,char *str){  if(T->data)free(T->data);  int i=0,j;  while(str[i]!='\0')i++;  if(!i){T->data=NULL;T->len=0;}  else{    T->data=(char*)malloc(i*sizeof(char));    for(j=0;j
        
         data[j]=str[j];    }    T->data[j]='\0';    T->len=i;  }  return OK;}int Index_SimpleMode(String T,String S,int pos){  if( S.len == 0 || T.len
        
       
      

 

设主串S的长度是n  子串T的长度是m

最好的情况是：主串为aaaaaabc， 子串为bc，此时执行的次数是 ( m + n ) / 2 

时间复杂度为O（n+m）

最坏的情况是：主串为000000001，子串为01，此时执行的次数是 m * ( n - m + 2 ) / 2

时间复杂度为O（m*n）

 

 

 

双向匹配算法

可以看到上面所示最坏的情况需要不断回滚，可以限制匹配成功的条件，也就是模式串的首尾同时匹配上

那么再继续进行匹配，这个算法我称其为双向匹配算法，先不管该算法有没有很牛的名字，其思路是在暴力

匹配的基础上加上 模式串的尾部也需要相同才算匹配成功，然后首尾两头向中间移动继续匹配字符，因此如果

模式串的一半长度匹配成功，那么另一半也就匹配成功，则返回成功匹配的索引值，否则返回-1

#include 
      
       #include 
       
        #define OK 1typedef int Status;typedef struct {  char *data;  int  len;}String;Status initString(String *T){  T->data = NULL;  T->len  = 0;  return OK;}Status strAssign(String *T,char *str){  if(T->data)free(T->data);  int i=0,j;  while(str[i]!='\0')i++;  if(!i){T->data=NULL;T->len=0;}  else{    T->data=(char*)malloc(i*sizeof(char));    for(j=0;j
        
         data[j]=str[j];    }    T->data[j]='\0';    T->len=i;  }  return OK;}int twoWayMode(String T,String S){  if(S.len > T.len)return -1;  int i=0, j=0, m=S.len-1, n=m/2;  int count = 0;  while(i
         
          n){  //improve;        printf("count is %d\n",++count);        return i-j;      }    }else{      i=i-j+1;  //rollback      j=0;    }    count++;  }  printf("calc: %d\n",count);  return -1;}int main(){  char str1[] = "ABCABd ABdsadA ABCAdsaABddsadasdaABCDsadCaDdsaABCDEFGH";  char str2[] = "ABCDEFGH";  String S1,S2;  initString(&S1);  initString(&S2);  strAssign(&S1,str1);  strAssign(&S2,str2);  int res = twoWayMode(S1,S2);  if(res>=0)printf("find it: %d\n",res);  else    printf("doesn't match\n");  return OK;}
         
        
       
      

其时间复杂度与暴力匹配的时间复杂度基本相同，但是新的算法的复杂度更接近于最好的情况也就是O（m + n）

 

KMP匹配算法

还有一种改进的算法是KMP算法，这个算法不太好理解

因此这里找了一篇看过中讲的最好的文章：

当然可以先看阮一峰的文章，方便理解：

#include 
      
       #include 
       
        #define OK 1typedef int Status;typedef struct {  char *data;  int  len;}String;Status initString(String *T){  T->data = NULL;  T->len  = 0;  return OK;}Status strAssign(String *T,char *str){  if(T->data)free(T->data);  int i=0,j;  while(str[i]!='\0')i++;  if(!i){T->data=NULL;T->len=0;}  else{    T->data=(char*)malloc(i*sizeof(char));    for(j=0;j
        
         data[j]=str[j];    }    T->data[j]='\0';    T->len=i;  }  return OK;} //next数组算法void getNext(String S,int *next){  next[0] = -1;  int k=-1, j=0;  while(j
         
          0)printf("find it :%d\n",res);  else printf("doesn't match\n");  return OK;}
         
        
       
      

事实上还有一种算法叫BM算法，这种算法的使用目前是多的，而且也比较容易理解，由于时间有限，下次在此补充，大家可以参考下面的连接

通常情况下，模式串的长度n 远小于 目标串的长度m ，因此KMP的算法时间复杂度为O（m）

 

欢迎各位转载，但请指明出处：