[数据结构][洛谷]P3375模板题 KMP

主要还是KMP算法,上学期没学,只是考前抱了抱佛脚,也没怎么弄明白.
先放代码:

//KMP

#include <bits/stdc++.h>//万能头

using namespace std;

string s,t;//s文本串,t模式串

//用char数组比较符合习惯,但是想试试string类

int nxt[100002];//在全局变量区,一般这个数组会初始化为全0

//getNext函数实际上就是让t自己与自己进行一个匹配.

void getNext(string& t)//一开始用的string* t,但好像不可以?

{

    nxt[0]=-1;

    int k=-1,j=0;

    while(j<t.length())//最初写的t.length()-1,答案不对,见main中的解释

    {

        if(k==-1||t[k]==t[j])//匹配成功,往后继续

        {

            j++;k++;

            //先++再给nxt数组赋值,因为我是按这个位置之前的字符串(不包括当前位置)的最长前后缀长度为此位置的nxt值

            nxt[j]=k;

        }

        else k=nxt[k];

        //意思是如果串的前后缀匹配到这里开始不等了,就寻找前面串里是否还有更小的前后缀(后面会图解)

    }

}

int KMP(string& s,string& t)//同样不知道为什么得用&引用才不报错

{

    int ls = s.length(),lt = t.length();

    int i=-1,j=-1;

    while(i<ls)

    {

        if(s[i]==t[j]||j==-1)

        {

            i++; j++;

        }

        else j = nxt[j];//匹配不上就把t串右移

        if(j==lt)//t被全部匹配上了

		{

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

			j = nxt[j];//继续找下一个匹配上的位置

		 }

    }

    if(j<lt) return -1;//最后没匹配上就返回-1

}

int main()

{

    cin>>s>>t;//太久不打,最初串流符号都打返了

    getNext(t);

    KMP(s,t);

    for(int i=1;i<=t.length();i++) printf("%d ",nxt[i]);

    //最后一行输出border,似乎是nxt,但又不真的是nxt

    //因为我的nxt其实求的是上一位的border...

    //所以从1号下标开始输出,这时候最后那个border会出现缺失(为0)情况

    //因为根本没算它,就是初始值.所以我在求nxt的时候又多求了一位

    //也就出现了getNxt函数中的t.length()没有减1...

}

我的理解:
①求nxt值时,刚开始很明显是要找到和开头一样的字母的第一个位置.
于是就有k=-1,j=0,先++再开始比较,此时k是0,j是1,如果匹配不成功,k就不断回到-1(因为nxt[0]是-1),j继续往后走,直到找到串的开头字母.
②然后就进行匹配成功的操作:k++,j++,如果匹配成功就继续比较下一位,如果失败就如下图所示:
绿色(深绿加浅绿)代表已经匹配好的t的子串,但是当k,j再右移的时候,两个"指针"指向的字母开始不同,这时候就寻找之前匹配过的串,看看有没有更短些的前后缀.也就出现了如图所示的k=nxt[k].

再看KMP算法的过程:
我觉得图已经很清晰了,后面看如果不懂的话再加文字吧…

巴特西

[数据结构][洛谷]P3375模板题 KMP

最新文章

热门文章