图解扩展kmp












#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 1000

using namespace std;
int next[MX],extend[MX];

void getnext(char *s,int next[]){
    int slen = strlen(s);
    next[0] = slen;
    int p = 0;
    while (p+1<slen && s[p]==s[p+1]) p++;
    next[1] = p;
    int k = 1, L;
    for (int i = 2; i<slen; i++){
        p = k+next[k]-1; L = next[i-k];
        if (i+L <= p) next[i] = L;
        else {
            int j = p-i+1;
            if (j < 0) j = 0;
            while (i+j<slen && s[i+j]==s[j]) j++;
            next[i] = j; k = i;
        } 
    }
}

void getextend(char *t,char *s,int extend[]){
    int slen = strlen(s) ,tlen = strlen(t);
    int p = 0;
    while (p<tlen && p<slen && t[p]==s[p]) p++;
    extend[0] = p;
    int k = 0, L;
    for (int i = 1; i<tlen; i++){
        p = k+extend[k]-1; L = next[i-k];
        if (i+L <= p) extend[i] = L;
        else {
            int j = p-i+1;
            if (j < 0) j = 0;
            while (i+j<tlen && j<slen && t[i+j] == s[j]) j++;
            extend[i] = j; k = i;
        } 
    }
}

int main()
{
    char s[MX],t[MX];
    cin>>s>>t;
    getnext(s,next);
    getextend(t,s,extend);
    for(int i=0;i<strlen(t);i++)cout<<extend[i]<<" ";cout<<endl;
    system("pause");
    return 0;
}
分类: 所有

2 条评论

konnyakuxzy · 2017年6月15日 2:45 下午

Orz,abs大佬の算法课堂!
太谢谢啦!

konnyakuxzy · 2017年6月12日 10:05 上午

Orz强记学算法中。。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *