KMP字符串模式匹配算法

《KMP字符串模式匹配算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、KMP算法是一种用于字符串匹配的算法,这个算法的高效之处在于当在某个位置匹配不成功的时候可以根据之前的匹配结果从模式字符串的另一个位置开始,而不必从头开始匹配字符串.因此这个算法的关键在于,当某个位置的匹配不成功的时候,应该从模式字符串的哪一个位置开始新的比较.假设这个值存放在一个next数组中,其中next数组中的元素满足这个条件:next[j]=k,表示的是当模式字符串中的第j+1个(这里是遵守标准C语言中数组元素从0开始的约定,以下不再说明)发生匹配不成功的情况时,应该从模式字符串的第k+1个字符开始新的匹配.如果已经得到了模式字符串的next数组,那么KMP算法的实

2、现如下://KMP字符串模式匹配算法//输入:S是主串,T是模式串,pos是S中的起始位置//输出:如果匹配成功返回起始位置,否则返回-1intKMP(PStringS,PStringT,intpos){assert(NULL!=S);assert(NULL!=T);assert(pos>=0);assert(poslength);if(S->lengthlength)return-1;printf("主串t=%s",S->str);printf("模式串t=%s",T->str);int*next=(int*)malloc(T->length*

3、sizeof(int));//得到模式串的next数组GetNextArray(T,next);inti,j;for(i=pos,j=0;ilength&&jlength;){//i是主串游标,j是模式串游标if(-1==j

4、

5、//模式串游标已经回退到第一个位置S->str[i]==T->str[j])//当前字符匹配成功{//满足以上两种情况时两个游标都要向前进一步++i;++j;}else//匹配不成功,模式串游标回退到当前字符的next值{j=next[j];}}free(next);if(j>=T->length){//匹配成功returni-T->

6、length;}else{//匹配不成功return-1;}}下面看看如何得到next数组.这是一个递推求解的过程,初始的情况是next[0]=-1.假设在某一个时刻有如下的等式成立:str[0...k-1]=str[j-k...j-1],那么next[j]=k,在这个前提下,继续进行下一个字符的匹配.1)如果str[0...k]=str[j-k...j],那么next[j+1]=next[j]+1=k+1.2)反之,如果上面的匹配不成立,那么就要从next[k]开始进行新的匹配,如果成功的话,那么:next[j+1]=next[next[j]]+1=next[k]+1;如

7、果还是不能匹配成功就再从next[next[k]]的位置开始进行的新的匹配,直到匹配成功为止.如果这个过程一直进行下去都没有找到可以成功匹配的字符的话,那么next[j+1]=0,这时表示要从字符串的第一个位置开始新的匹配了.用一个公式表示上述的算法,那么可以写作:next[j]=1)-1,当j=0时;2)Max{k

8、0<=k

9、ssert(NULL!=pstr);assert(NULL!=next);assert(pstr->length>0);//第一个字符的next值是-1,因为C中的数组是从0开始的next[0]=-1;for(inti=0,j=-1;ilength-1;){//i是主串的游标,j是模式串的游标//这里的主串和模式串都是同一个字符串if(-1==j

10、

11、//如果模式串游标已经回退到第一个字符pstr->str[i]==pstr->str[j])//如果匹配成功{//两个游标都向前走一步++i;++j;//存放当前的next值为此时模式串的游标值next[i]=j;

12、}else//匹配不成功j就回退到上一个next值{j=next[j];}}}完整算法如下：#include#include#include#include#defineMAX_LEN_OF_STR30//字符串的最大长度typedefstructString//这里需要的字符串数组,存放字符串及其长度{charstr[MAX_LEN_OF_STR];//字符数组intlength;//字符串的实际长度}String,*PString;/