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

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

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

//KMP 
#include //万能头
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>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算法的过程:
我觉得图已经很清晰了,后面看如果不懂的话再加文字吧…