编程 7

_7_线性结构_字符串_模式匹配编程

  发现国内没有好的关于字符串处理的书籍,找了好久没有找到,不知道哪位大侠能介绍一本中文版的,英语的看的速度太慢。

一. KMP算法

下面是我测试的字符串模式匹配源代码

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,简称KMP算法。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。

【Version 1】

二. KMP算法的意义

    这个测试的时候,受北大那个视屏的影响,这个调试了老久没成功。最终虽然也能运行了,但是感觉怪怪的。

先举一个简单模式匹配的例子,给定字符串T=“abababca”,S=“bacbababaabcbab”,判断T是否是S的子串,如果用暴力扫描的话,就是拿着T字符串从S的头扫到尾。这样的时间复杂度最坏情况下是O(n*m),其中n和m分别是主串和模式串的长度。而KMP算法的时间消耗是O(n+m)的,至于为什么这样,下面再说。

/*    本程序测试字符串的各种处理函数和操作*/#include <stdio.h>#include <stdlib.h>#include <string.h>//******************************************************0//            定义用户数据类型typedef long int LINT;typedef enum {FALSE,TRUE} BOOL;//******************************************************1//******************************************************0LINT StringMatch(char* String,char* subString,LINT StartIndex);LINT StringMatchRecall(char* String,char* subString,LINT StartIndex);BOOL SubStringMatchHead(char* String,char* subString);int GetMaxSubStringLen(const char* string);LINT StringMatchKMP(const char* String,char* subString,LINT StartIndex);int main(int argc,char* argv[]){    int x;    x=StringMatch("abcdefghijabcdabmn","abcdab",0);        printf("%d \n",x);    x=StringMatchRecall("abcdefghijabcdabmn","mn",0);        printf("%d \n",x);    /*    if(SubStringMatchHead("abcdefg","abc"))        printf("%d \n",1);    x=GetMaxSubStringLen("abcdefgabc");        printf("%d \n",x);       */    getchar();    getchar();    return 0;}//******************************************************1//******************************************************0/*函数功能:    模式匹配朴素算法:双循环函数原型:    LINT StringMatch(char* String,char* subString,LINT StartIndex)函数参数:    char* String:字符串    char* subString:模式字符串    LINT StartIndex:搜索开始索引返回值:    如果匹配成功,则返回模式字符串在字符串中开始的首地址;    如果匹配失败,则返回-1异常:    无*/LINT StringMatch(char* String,char* subString,LINT StartIndex){    LINT i;    int  j;    LINT LastIndex;    int  subStrLen;    //检查指针有效性和空串    //其实这里也可以不检测  StartIndex>strlen-strlen(subString)    if( !String || !subString || !String[0] || !subString\        || StartIndex > strlen-strlen(subString)\      )        return -1;    LastIndex=strlen-strlen(subString);    subStrLen=strlen(subString);    for(i=StartIndex;i<=LastIndex;i++)    {        for(j=0;j<subStrLen;j++)        {            if(String[i+j] - subString[j])                break;        }        if(j==subStrLen)  //这么判断因为要结束循环正好相等            return ++i;  //这个地方不能用i++    }    return -1;}//******************************************************1//******************************************************0/*函数功能:    模式匹配朴素算法:单循环回溯函数原型:    LINT StringMatchRecall(char* String,char* subString,LINT StartIndex)函数参数:    char* String:字符串    char* subString:模式字符串    LINT StartIndex:搜索开始索引返回值:    如果匹配成功,则返回模式字符串在字符串中开始的首地址;    如果匹配失败,则返回-1异常:    无*/LINT StringMatchRecall(char* String,char* subString,LINT StartIndex){    LINT i;    LINT LastIndex;    int  j;    int  SubStrLen;    int  StringLen;    //检查指针有效性和空串    //其实这里也可以不检测  StartIndex>strlen-strlen(subString)    if( !String || !subString || !String[0] || !subString\        || StartIndex>strlen-strlen(subString)\      )  return -1;    i=StartIndex;    j=0;    SubStrLen=strlen(subString);    StringLen=strlen;    LastIndex=strlen - SubStrLen ;        while( i<=StringLen  && j<=SubStrLen)    {            if(String[i] == subString[j] )        {            if(j==SubStrLen-1)                return i-j+1;            ++i;            ++j;        }        else        {                        i=i-j+1;  //回溯              j=0;        }    }        return -1;}//******************************************************1

三. KMP算法的核心

  

KMP的核心就是一张表,我们称之为部分匹配表,起初我看这张表的时候也是云山雾绕,不知所云,部分匹配表是为模式串T专门设计的,T中每个字符对应着一个整数值,(这个地方也是困扰了我很久),现在我尽可能说得明白一些。首先下面附上一张T为“abababca”的部分匹配图,让大家“先睹为快”,看看部分匹配表是个什么东东。

    下面是后来调试的源代码,经过测试能得到正确的结果。

编程 1

 /*    本程序测试字符串的各种处理函数和操作*/#include <stdio.h>#include <stdlib.h>#include <string.h>//******************************************************0//            定义用户数据类型typedef long int LINT;typedef enum {FALSE,TRUE} BOOL;//******************************************************1//******************************************************0int StringMatch(char* String,char* subString,int StartIndex);int StringMatchRecall(char* String,char* subString,int StartIndex);BOOL  StrMatch(char* string,char* subStr,int len);//BOOL  GetStrNextJ(char* string,int* nextJ);int main(int argc,char* argv[]){    int x;    int i;    int arrayNum[100]={0};     x=StringMatch("abcdefghijklmn","lm",0);        printf("%d \n",x);    x=StringMatchRecall("abcdefghijklmn","x",0);        printf("%d \n",x);    if(StrMatch("abcdefg","bc",strlen("bc")))        printf("Match");    else        printf("Not match");    putchar(13);    getchar();    getchar();    return 0;}//******************************************************1//******************************************************0/*函数功能:    模式匹配朴素算法:双循环函数原型:    int StringMatch(char* String,char* subString,int StartIndex)函数参数:    char* String:字符串    char* subString:模式字符串    int StartIndex:搜索开始索引返回值:    如果匹配成功,则返回模式字符串在字符串中开始的首地址;    如果匹配失败,则返回-1异常:    无*/int StringMatch(char* String,char* subString,int StartIndex){    int i,        j;    int StrLen,        SubStrLen;    StrLen=strlen;    SubStrLen=strlen(subString);    //检查指针有效性和空串    //其实这里也可以不检测  StartIndex>strlen-strlen(subString)    if( !String || !subString || !String[0] || !subString\        || StartIndex > StrLen-SubStrLen\      )        return -1;    for(i=StartIndex;i<= StrLen - SubStrLen ;i++)    {        for(j=0; j < SubStrLen ;j++)        {            if(String[i+j] - subString[j])                break;        }        if(j==SubStrLen)  //这么判断因为要结束循环正好相等            return ++i;  //这个地方不能用i++    }    return -1;}//******************************************************1//******************************************************0/*函数功能:    模式匹配朴素算法:单循环回溯函数原型:    int StringMatchRecall(char* String,char* subString,LINT StartIndex)函数参数:    char* String:字符串    char* subString:模式字符串    int StartIndex:搜索开始索引返回值:    如果匹配成功,则返回模式字符串在字符串中开始的首地址;    如果匹配失败,则返回-1异常:    无*/int StringMatchRecall(char* String,char* subString,int StartIndex){    int i,        j;    int StrLen,        SubStrLen;    StrLen=strlen;    SubStrLen=strlen(subString);    //检查指针有效性和空串    //其实这里也可以不检测  StartIndex>strlen-strlen(subString)    if( !String || !subString || !String[0] || !subString\        || StartIndex > StrLen-SubStrLen\      )  return -1;    i=StartIndex;    j=0;    while( i < StrLen  )    {        if(String[i] == subString[j] )        {            ++j;            ++i;                     }        else        {            i=i-j+1;  //回溯            j=0;        }        if(j==SubStrLen)            return i-j+1;    }    return -1;}//******************************************************1//******************************************************0/*函数功能:    判断字符串String和subStr是否相等; 相当于strcmp函数,    但是这个函数需要传递3个参数函数原型:    BOOL  StrMatch(char* string,char* subStr,int len)函数参数:    char* string:字符串1    char* subStr:字符串2,字符串string的子串    int len:字符串2的长度返回值:    如果匹配成功则返回TRUE,否则返回FALSE;异常:    无*/BOOL  StrMatch(char* string,char* subStr,int len){    int i;    if(!string || !subStr || strlen(string)<=len)        return FALSE;    i=0;    while(i<len)    {        if(string[i] != subStr[i])            return FALSE;  //比较过程中,如果出现不匹配现象就返回        i++; //如果相等就继续比较    }    return  TRUE;}//******************************************************1

好了,现在我们有了一个含有8个字符的模式串T,那么最后一行的value值是怎么得来的呢?别急,我先介绍相关概念:前缀和后缀,就拿字符串”abca“来说,”abca“的前缀有{a,ab,abc},”abca”的后缀有“bca,ca,a”,怎么样,很好理解对吧?一个字符串的前缀就是除了该字符串的最后一个字符以外的从首字符开始的连续字符串(自己胡乱下的定义,可能不准确,不过没关系,理解意思就行),后缀定义也类似。那么像字符串”a“就既没有前缀也没有后缀。

  这里原本要调试KMP算法的,但是调试了很久都没有成功,主要是自己还没有完全理解KMP算法的思路,只能等到以后慢慢替换了。

有了上面这两个概念,我们就可以得出value是怎么来的了。value值就是”前缀”和”后缀”的最长的共有元素的长度,这里就直接讲解例子帮助消化理解。首先我们把目光聚焦到index=0位的字符‘a’上来,字符串”a“没有前缀,没有后缀,共有元素为0,所以value[0]=0。然后index=1,字符串”ab“,前缀集合为{a},后缀集合为{b},没有共有元素,value[1]=0。index=2,字符串“aba”,前缀集合为{a,ab},后缀集合为{ba,a},共有元素为{a},取长度最长的,所以value[2]=1.
index=3,字符串“abab”,前缀集合为{a,ab,aba},后缀集合为{bab,ab,b},共有元素为{ab},value[3]=2.
index=4,字符串“ababa”,前缀集合为{a,ab,aba,abab},后缀集合为{baba,aba,ba,a},共有元素为{aba},所以value[4]=3.
index=5,字符串“ababab”,前缀集合为{a,ab,aba,abab,ababa},后缀集合为{babab,abab,bab,ab,b},共有元素是{abab,ab},value[编程,5]=4.
index=6,字符串“abababc”,前缀集合是{a,ab,aba,abab,ababa,ababab},后缀集合是{bababc,ababc,babc,abc,bc,c},没有共有元素,所以value[6]=0.
index=7,字符串“abababca”,前缀集合是{a,ab,aba,abab,ababa,ababab,abababc},后缀集合是{bababca,ababca,babca,abca,bca,ca,a},共有元素是{a},value[7]=1.这下算出value来应该是驾轻就熟了吧。

看来园子里部分大侠的代码和分析,还是不甚理解KMP算法。

四. KMP算法运行

部分匹配表我们已经可以算出来了,现在就是要用这张表来运行KMP算法。这里以T=“abcdabd”,S=“abcdab
abcdabcdabde”为例说明,这里首先给出T的部分匹配表:

编程 2

 

编程 3

初始状态,‘d’和‘
’不匹配,但是‘d’前面的部分“abcdab”匹配,所以我们查询部分匹配表,得到value[5]=2,所以我们把T向右移动(6-2)个单位,6是部分匹配的长度,2是部分匹配字符串的value值。

编程 4

如红线标注,’c‘和’
‘不匹配,但是’c‘前面部分“ab”部分匹配,所以我们查表,得到value[1]=0,所以我们吧T向右移动(2-0)个单位。2是部分匹配的长度,0表示value值。

编程 5

如红线标注,’a‘和’
‘不匹配,而且’a‘前面什么也没有,就也没有部分匹配,那部分匹配表中查不到怎么办呢?对于这种情况,我们默认是T向右移动一个单位。

编程 6

如红线所示,’c‘与’d‘不匹配,但是T中’d’以前的部分”abcdab“匹配了,所以我们查询部分匹配表,value[5]=2,所以模式串T向右移动(6-2)个单位。

编程 7

“SUCCESS!”,我们找到了S的子串与T相等。如果你只想找到S中的一处与T相等,那么你就可以终止算法了,如果你还想找到S中第二个出现“ancdabd”的位置,那么你就向右移动(7-0)位,后面的过程和上面一样的,这里就不再赘述。

五. 总结

可能大家会发现部分匹配表与我们在书本上或者一些博客上看到的不一样,书本上用的是next数组,next[x]中的x表示的是匹配失败处字符的下标,假设我们在匹配的过程中发现T[x]!=S[i]
(1<=i<=s.len),那么我们就查看T[1],T[2],…T[x-1]的部分匹配值,对!,就是上面讲的部分匹配表!回顾上面的例子我们可以发现,当T[x]处匹配失败时,我们查看的value[x-1]处的值,换言之,next[x]=value[x-1]!!。所以我们会看到next[0]=-1,因为没有value[-1]这种东西嘛~~。

六. next数组的源代码

 1 void getNext(char *T){
 2     int j=0,k=-1;
 3     next[0]=-1;
 4     while(j<strlen(T)-1){
 5         if(k==-1||T[j]==T[k]){
 6             j++; k++;
 7             next[j]=k;
 8         }
 9         else k=next[k];    
       }
11 }