KMP算法(刘汝佳算法书学习)

2017年7月23日 7点热度 0条评论 来源: 三茶先生

KMP理解:


假定在匹配中,正在比较的文本串位置和模板串abbaaba最后一个字符不符合(失配),这是朴素算法会将模板串右移一位,继续比较,但是kmp不这样做,kmp认为既然!!位置已经比较过,应该可以利用模板串本身属性判断出右移一位不能匹配,同理,右移两位或者三位也不行,但是右移四位是有可能的。这个时候,需要比较 ‘’‘’*处的字符和abbaaba的第三个字符。

下面那个链状图就是一个状态机,其中编号为i的节点表示已经匹配了i个字符,匹配开始是0,如果成功匹配则+1,失配时‘沿着失配边走’,如果在状态6处失配,应转到状态2.。为了方便,这里使用失配函数f[i]表示状态i失配时应转移到的新状态,要特别注意的是f[0]=0。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
void getFail(char* p,int* f)
{
    int m=strlen(p);
    f[0]=0,f[1]=0;
    for(int i=1;i<m;i++)
    {
        int j=f[i];
        while(j&&p[i]!=p[j])
        j=f[j];
        f[i+1]=p[i]==p[j]?j+1:0;
    }
}///打出状态转移表(next数组求)/(失配边)

void get_next(char* T,char* P,int* f)
{
    int n=strlen(T),m=strlen(P);
    getFail(P,f);
    int j=0;
    //printf("11111111");
    for(int i=0;i<n;i++)
    {
        while(j&&P[j]!=T[i])
        j=f[j];
        if(P[j]==T[i])
        j++;
        if(j==m)
        printf("子串位置: %d\n",i-m+1);
    }
}//两串比较开始跳跃寻找子串位置

int main()
{
    char str[13]={
  "ABRACADABRA"};
    char str2[4]={
  "CAD"};
    int f[20]={
  0};
    getFail(str,f);
    printf("状态转移方程:\n");
    for(int i=0;i<12;i++)
    {
        printf("%d",f[i]);
    }
    cout<<endl;
    get_next(str,str2,f);
    return 0;
}

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