KMP是一个困扰我很久的算法，听老师或者是学姐讲了差不多有4次了，但是还是搞不太懂，今天终于，终于，终于搞懂了！

　　　　　　　　　　　　　　　　　　　　　　　　　　——2017-10-29 Vanora

首先推荐一下KMP详解——July

读罢之后内心只有一个感觉：我的KMP终于可以毕业了qwq

学东西千万不要求快!细细地，慢慢地去读这篇文章，相信你也可以从头到尾彻底理解KMP算法呦~

接下来是一些KMP的练手题:

做完这些并且真正搞懂之后，相信你一定就会KMP算法了~（一定要理解了，吃透了！）

1.P3375 【模板】KMP字符串匹配

直通车

思路:

　　真正意义上的KMP板子题，很良心（不加优化版）

新知识Get!!!:

　　char数组不清零，直接用cin读入的话，自动清零！！！好厉害的样子！！！

坑点:

　　一定要真正理解nxt[]求得到底是什么，是用匹配串求解还是用文本串

上代码:

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int M = ;

char s[M],p[M];

int lens,lenp;

int nxt[M];

void getnxt() {

    int k=-,j=;

    nxt[]=-;

    while(j<lenp) {

        if(k==- || p[j]==p[k]) {

            j++;k++;

            nxt[j]=k; //记录更新的nxt值

        }

        else k=nxt[k];

    }

}

void KMP() {

    int i=,j=;

    while(i<lens) {

        if(j==- || s[i]==p[j]) i++,j++;

        //j==-1:没有nxt,所以从一开始进行匹配

        //s[i]==p[j]:当前文本串与匹配串的位置上的字符匹配成功,继续匹配

        else j=nxt[j]; //寻找更短的公共前后缀

        if(j==lenp) {

            printf("%d\n",i-lenp+);

            i--; //文本串之前已经匹配过了,所以没有再次进行匹配的需要了

            j=; //匹配串从新开始进行匹配

        }

    }

} 

int main() {

    cin>>s>>p;

    lens=strlen(s);

    lenp=strlen(p);

    getnxt();

    KMP();

    for(int i=; i<=lenp; i++) printf("%d ",nxt[i]);

    return ;

}

2.POJ 3461 Oulipo

直通车

思路:

　　用KMP来做，如果成功匹配，那么ans++，最后输出ans即可

坑点:

　　①注意他的输入顺序。。。。。。

　　②注意是多组数据输入。。。。。

　　③该题用上述优化过的方法都过不了。。。。

　　④该题数据范围一定要看好了。。。

　　⑤W，T范围是不同的。。

　　⑥最好不要用gets读入。

上代码:

1）while版（mine）

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int M = ;

const int N = ;

char s[M],p[N];

int T,ans,lens,lenp;

int nxt[N];

void getnxt() {

    int k=,j=;

    nxt[]=-;nxt[]=;

    while(j<lenp) {

        if(k==- || p[j]==p[k]) {

            k++,j++;

            nxt[j]=k;

        }

        else k=nxt[k];

    }

}

void KMP() {

    int i=,j=;

    while(i<lens) {

        if(s[i]==p[j]) i++,j++;

        else if(j>=) j=nxt[j];

        else i++,j=;

        if(j==lenp) ans++,j=nxt[j];

    }

} 

int main() {

    scanf("%d",&T);

    while(T--) {

        scanf("%s%s",p,s);

        lens=strlen(s);

        lenp=strlen(p);

        getnxt();

        KMP();

        printf("%d\n",ans);

        ans=;

    }

    return ;

}

2）从网上学到的另外一种方法，感觉十分类似，然而能AC。。。服气。。。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int M = ;

const int N = ;

char s[M],p[N];

int ans,lens,lenp;

int nxt[N];

void getnxt() {

    int k=,j;

    nxt[]=-;nxt[]=;

    for(j=; j<=lenp; j++) {

        while(k>= && p[k]!=p[j-]) k=nxt[k];

        nxt[j]=++k;

    }

}

void KMP() {

    int i=,j=;

    while(i<lens) {

        if(s[i]==p[j]) i++,j++;

        else if(j>=) j=nxt[j];

        else i++,j=;

        if(j==lenp) ans++,j=nxt[j];

    }

} 

int main() {

    int T;

    scanf("%d",&T);

    while(T--) {

        scanf("%s%s",p,s);

        lens=strlen(s);

        lenp=strlen(p);

        getnxt();

        KMP();

        printf("%d\n",ans);

        ans=;

    }

    return ;

}

3）采用for循环的一种方法

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int M = ;

const int N = ;

int T,ans,lens,lenp;

char s[M],p[N];

int nxt[N];

void getnxt() {

    nxt[]=;

    for(int i=; i<lenp; i++) {

        int j=nxt[i];

        while(j && p[i]!=p[j]) j=nxt[j];

        nxt[i+] = p[i]==p[j] ? j+ : ;

    }

}

void KMP() {

    int j=;

    for(int i=; i<lens; i++) {

        while(j && (p[j]!=s[i])) j=nxt[j];

        if(p[j]==s[i]) j++;

        if(j==lenp) ans++;

    }

}

int main() {

    scanf("%d",&T);

    while(T--) {

        memset(nxt,,sizeof(nxt));

        ans=;

        scanf("%s%s",p,s);

        lenp=strlen(p);

        lens=strlen(s);

        getnxt();

        KMP();

        printf("%d\n",ans);

    }

    return ;

}

3.P1308 统计单词数

直通车

思路:

　　①因为会出现空格，所以手动将s，p的左右均+' '，然后再进行KMP即可

　　②不需要+' '，直接在KMP匹配成功之后判断是否s左右均拥有' '即可

　　　　　　不过需要注意的是：当在一开头就匹配成功的时候则只需要判断是否s右边有' '即可

坑点:

　　千万不要用gets进行输入，会编译错误。。。。

上代码:

①

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <algorithm>

using namespace std;

const int pl = ;

int lens,lenp,ans=-,firsta=-;

string s,p;

int nxt[pl];

void getnxt() {

    int k=,j=;

    nxt[]=-,nxt[]=;

    while(j<lenp) {

        if(k==- || p[k]==p[j]) {

            k++,j++;

            nxt[j]=k;

        }

        else k=nxt[k];

    }

}

void KMP() {

    int i=,j=;

    while(i<lens) {

        if(s[i]==p[j]) i++,j++;

        else if(j>=) j=nxt[j];

        else i++,j=;

        if(j==lenp) {

            if(firsta==-) firsta=i-j;

            ans++,j=nxt[j];

        }

    }

}

void tochange(string &a,int len) {

    for(int i=; i<len; i++) {

        if(a[i]==' ') continue;

        int x=a[i]-'A';

        if(x>=) x-=;

        char y=x+'a';

        a[i]=y;

    }

}

int main() {

    getline(cin,p);

    p=' '+p+' ';

    lenp=p.length();

    tochange(p,lenp);

    getline(cin,s);

    s=' '+s+' ';

    lens=s.length();

    tochange(s,lens);

    getnxt();

    KMP();

    if(ans==-) printf("%d",ans);

    else printf("%d %d",ans+,firsta);

    return ;

}

②

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <algorithm>

using namespace std;

const int pl = ;

int lens,lenp,ans=-,firsta=-;

string s,p;

int nxt[pl];

void getnxt() {

    int k=,j=;

    nxt[]=-,nxt[]=;

    while(j<lenp) {

        if(k==- || p[k]==p[j]) {

            k++,j++;

            nxt[j]=k;

        }

        else k=nxt[k];

    }

}

void KMP() {

    int i=,j=;

    while(i<lens) {

        if(s[i]==p[j]) i++,j++;

        else if(j>=) j=nxt[j];

        else i++,j=;

        if(j==lenp && s[i]==' ') {

            if(i>j && s[i-j-]==' ') {

                if(firsta==-) firsta=i-j;

                ans++,j=nxt[j];

            } else {

                if(i==j) {

//              if(i==0) { //等价

                    if(firsta==-) firsta=i-j;

                    ans++,j=nxt[j];

                }

            }

        }

    }

}

void tochange(string &a,int len) {

    for(int i=; i<len; i++) {

        if(a[i]==' ') continue;

        int x=a[i]-'A';

        if(x>=) x-=;

        char y=x+'a';

        a[i]=y;

    }

}

int main() {

    getline(cin,p);

    lenp=p.length();

    tochange(p,lenp);

    getline(cin,s);

    lens=s.length();

    tochange(s,lens);

    getnxt();

    KMP();

    if(ans==-) printf("%d",ans);

    else printf("%d %d",ans+,firsta);

    return ;

}

巴特西

【説明する】KMP

接下来是一些KMP的练手题:

做完这些并且真正搞懂之后，相信你一定就会KMP算法了~（一定要理解了，吃透了！）

1.P3375 【模板】KMP字符串匹配

直通车

思路:

新知识Get!!!:

坑点:

上代码:

2.POJ 3461 Oulipo

直通车

思路:

坑点:

上代码:

3.P1308 统计单词数

直通车

思路:

坑点:

上代码:

最新文章

热门文章