【KMP】
学习KMP，我们先要知道KMP是干什么的。
KMP？KMPLAYER?看**?
正如AC自动机，KMP为什么要叫KMP是因为它是由三个人共同研究得到的- .-
啊跑题了。
KMP就是给出一个母串S和串T，然后看T是不是S的子串。
易想到朴素算法，且时间复杂度是明显的O(NM).
那么为什么KMP的复杂度会这么高呢？
因为每次失配的时候，指针只是简单的把在S串的指针向后移动一位，T串回到开头，其中对于子串T已匹配过的信息没有充分利用。
KMP是干嘛的？
利用一个next数组使得失配时T的指针不是简单的移动到开头而是移动到T串的某个以匹配位置上。
在这里还是来说明一下怎么利用next数组吧。
先来说说next数组吧，下面给出T串为abcababdb的各next[i]值。
next数组的意义:当当前位的后一位失配的时候指针应该移动到的位置。
具体怎么用呢？
我们设S:abcdabcababcababdb
T还是那个T。
好了，基本就是这些吧。。代码还是贴一贴，为了一些还是不太理解的同学加(chao)深(dai)理(ma)解。什么？next数组怎么求？把t和自己kmp一次就可以啦。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath> using namespace std;; char p[],s[]; int next[]; void make_next()
{
for(int q=,k=;q<strlen(p);q++)
{
while(k&&p[q]!=p[k]){
k=next[k-];
}
if(p[q]==p[k]){
k++;
}
next[q]=k;
}
} int main()
{
scanf("%s%s",p,s);
make_next();
for(int i=,k=;i<strlen(s);i++)
{
while(k&&s[i]!=p[k])
k=next[k-];
if(s[i]==p[k])k++;
if(k==strlen(p)){
printf("%d\n",i+-strlen(p));
}
}
return ;
}
【扩展KMP】
【trie】
【SA】
【ACAM】
待学习。。
【SAM】
待学习。。
貌似好久没写blog了。。
先挖个大坑慢慢更新。。。