KMP算法--C语言

字符串匹配问题:假设文本是一个长度为n的数组T[0...n-1],而模式是一个长度为m的数组P[0...m-1],其中m<=n,如果存在s(0<=s<=n-m),并且T[s...s+m-1]=P[0...m-1],那么称模式P在文本T中出现,且P在T中出现的位置是以s开始的。找出所有模式P在T中出现的开始位置。

KMP算法是解决字符串匹配问题的高效算法,之前我曾经编写过KMP算法,但是对该算法的理解却不够深,今天结合<<算法导论>>和个人的理解,对这个算法进行记录。

KMP算法力求匹配了的字符串,不再进行比较,意思是:如果现在T和P已经匹配到了P[i+1],即已经确定P[0...i]=T[s...s+i],那么如果如果此时P[i+1] != T[s+i+1],那么将T[s+i+1]和P[ prefix[i] ]相比较,而第一步就是要求prefix[i]的,prefix[i]数组中保存的是:当只有p[0...i]的字符串时,此时,p[0...i]的后部的字符串与p[0...i]的前部的字符串匹配的最大长度,(不包含自身与自身匹配的情况)

求ababaca的最长匹配的字符串的长度:

p[0]时的最长匹配的字符串的长度明显为0,

p[0...1]时的最长匹配的字符串的长度也明显为0,

当已经匹配了P[0...2]时:

当已经匹配了P[0...4]时:

计算前P[0...i]( 0=<i<=m-1)的最长匹配字符串的长度代码:

void kmpPrefixFunction(char *p,int length,int *prefix)
{
    prefix[0]=0;
    int k = 0;//前缀的长度
    for(int i=1; i<length; i++)
    {
        while(k>0&&p[k]!=p[i])
        {
            k=prefix[k-1];
        }
        if(p[k]==p[i])//说明p[0...k-1]共k个都匹配了
        {
            k=k+1;
        }
        prefix[i]=k;
    }
}

当我们的模式P[0...i-1]已经与S[k...k+i-1]中的字符匹配了,当p[i]不能与S[k+i]匹配时,我们不能无视S[k...k+i-1],将P直接向右移动i-1个字符,直接令s[k+i]与p[0]比较,是因为可能S[k...k+i-1]的后部字符串可能和P的前部字符串相匹配,如下图匹配到P[5]时,与S不匹配了,但这时S的后部与P[0...3]匹配了。/微笑,这时大家应该感觉到刚才求得的prefix[]数组的作用了吧!! 当S[i]!=p[pPoint]时,令pPoint=prefix[pPoint-1],接下来继续将S[i]与p[pPoint]相比较,不行,再令pPoint=prefix[pPoint-1]...(当pPoint等于0时,说明,S后部没有和P前部匹配的,就可以无视已经匹配的S[k...k+i-1]了,直接s[k+i]与p[0]比较了)

匹配函数的源代码:

void kmpMatch(char * s,int sLength,char * p,int pLength,int *prefix)
{
    int pPoint=0;
    for(int i=0; i<=sLength-pLength;i++)
    {


        while(pPoint!=0&&(s[i]!=p[pPoint]))
        {
            pPoint = prefix[pPoint-1];
        }
        if(s[i]==p[pPoint])
        {
            pPoint++;
            if(pPoint == pLength)
            {
                printf("找到:%d \n",i-pPoint+1);
                //pPoint = 0;//上一个在s匹配的字符串,不能成为下一个匹配字符串的一部分
                pPoint=prefix[pPoint-1];//上一个在s匹配的字符串,也能成为下一个匹配字符串的一部分
            }
        }


    }
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


void kmpMatch(char * s,int sLength,char * p,int pLength,int *prefix)
{
    int pPoint=0;
    for(int i=0; i<=sLength-pLength;i++)
    {


        while(pPoint!=0&&(s[i]!=p[pPoint]))
        {
            pPoint = prefix[pPoint-1];
        }
        if(s[i]==p[pPoint])
        {
            pPoint++;
            if(pPoint == pLength)
            {
                printf("找到:%d \n",i-pPoint+1);
                //pPoint = 0;//上一个在s匹配的字符串,不能成为下一个匹配字符串的一部分
                pPoint=prefix[pPoint-1];//上一个在s匹配的字符串,也能成为下一个匹配字符串的一部分
            }
        }


    }
}

void kmpPrefixFunction(char *p,int length,int *prefix)
{
    prefix[0]=0;
    int k = 0;//前缀的长度
    for(int i=1; i<length; i++)
    {
        while(k>0&&p[k]!=p[i])
        {
            k=prefix[k-1];
        }
        if(p[k]==p[i])//说明p[0...k-1]共k个都匹配了
        {
            k=k+1;
        }
        prefix[i]=k;
    }
}


//匹配函数的朴素算法,用于比较
void normal_match(char * s,int sLength,char * p,int pLength){
    int k;
    for(int i=0;i<sLength-pLength+1;i++){
        for(k=0;k<pLength;k++){
            if(s[i+k]!=p[k]){
                break;
            }
        }
        if(k==pLength){
            printf("找到:%d \n",i);
        }

    }
}


int main()
{
    char *s = "ababacababababababbaabbababaabaababacabababababbcababbabababcababba";
    char *p = "ababacab";
    int pLength = strlen(p);
    int *prefix = (int *)malloc(pLength*sizeof(int));
    kmpPrefixFunction(p,pLength,prefix);
    printf("字符串的最长前缀长度分别是:");
    for(int i=0; i<pLength; i++)
    {
        printf("%d\t",prefix[i]);
    }
    printf("\n使用KMP匹配\n");
    kmpMatch(s,strlen(s),p,pLength,prefix);

    printf("使用朴素算法:\n");
    normal_match(s,strlen(s),p,pLength);

    return 0;
}