字符串匹配-KMP算法

2017年10月24日 1点热度 0条评论 来源: 哇-WA

题目要求:给你两个字符串T,P。查找T串中是否存在P串。

一般思路:从T的第一个元素开始遍历,不断匹配P中的元素,如果当前位置元素匹配失败了,就重新从P的第一个元素开始匹配。

#include <stdio.h>
#include<string.h>
char P[105],T[105];
int main()
{
    scanf("%s%s",T,P);
    int n=strlen(T),m=strlen(P);
    for(int i=0; i<n ;i++)
    {
        int j=0;
        while(T[i+j]==P[j]) j++;
        if(j==m)
        {
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}

代码大致是这样。
// T = ABCDABCDABDE
// P = ABCDABD

比如这组实例。当T遍历到标记位置的C时,会重新从P的开头开始匹配。但是如果能够将前面几个已经匹配的元素的信息利用起来,就可以减少许多不必要的匹配。

例如可以发现C前面的AB是在P串中的开头两个元素,这时就可以直接从P中的第三个位置开始匹配。这时巧合吗?不是。因为匹配到C时,前面的AB已经确定匹配了,而P前两个元素与第5、6个元素相同,都是AB,所以这时我们就可以直接跳到P的第三个位置。

这时我们需要一个辅助数组来存储失配时转移的位置下标,我们称为适配函数。

失配函数的计算方法:

void getFail()
{
    int len=strlen(P);
    f[0]=f[1]=0;
    for(int i=1;i<len;i++)
    {
        //如果i点匹配失败,寻找对应的匹配点
        int j=f[i];
        //如果j点在上一个匹配点依然失败,则继续向上寻找当前点的匹配点,直到匹配或达到起始点。
        while(j && P[j]!=P[i]) j=f[j];
        //更新下一个失配点,如果本失配点找到了匹配点,则下一个失配值需要更新到匹配点+1;如果没有找到匹配点,则更新到起点。
        f[i+1] = P[j]==P[i]? j+1:0;
    }
}
ABCDABD
0000012

这是P的失配函数值,可以思考一下为什么会是这个值。


匹配函数find()与getFail()写法相似,可以将失配函数看为模式串P自己匹配自己。

寻找第一次匹配时起始元素的下标。

void find()
{
    int n=strlen(T),m=strlen(P);
    int j=0;
    for(int i=0;i<n;i++)
    {
        //如果T[i]匹配失败,则向上寻找前面的匹配点
        while(j && P[j]!=T[i]) j=f[j];
        //如果找到了一个匹配点,则将j后移一位(即继续匹配下一位)
        if(P[j]==T[i]) j++;
        //如果P已经匹配完了,则输出此串在T串中的起始位置
        if(j==m) printf("%d\n",i-m+1);
    }
}

返回匹配成功的次数

int find()
{
    int j=0,cnt=0;
    for(int i=0;i<n;i++)
    {
        //如果T[i]匹配失败,则向上寻找前面的匹配点
        while(j && P[j]!=T[i]) j=f[j];
        //如果找到了一个匹配点,则将j后移一位(即继续匹配下一位)
        if(P[j]==T[i]) j++;
        
        if(j==m) cnt++,j=f[j];
    }
    return cnt;
}

事实上这个算法不是完整的KMP算法,这是MP算法,KMP算法对失配函数做了更多的优化,但是一般来说MP算法已经比朴素算法快多了。



    原文作者:哇-WA
    原文地址: https://blog.csdn.net/u013852115/article/details/78335097
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。