【string】KMP, 扩展KMP,trie,SA,ACAM,SAM,最小表示法

时间:2021-11-07 12:25:26

【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]值。

【string】KMP, 扩展KMP,trie,SA,ACAM,SAM,最小表示法

  next数组的意义:当当前位的后一位失配的时候指针应该移动到的位置。

  具体怎么用呢?

  我们设S:abcdabcababcababdb

  T还是那个T。

  【string】KMP, 扩展KMP,trie,SA,ACAM,SAM,最小表示法

  【string】KMP, 扩展KMP,trie,SA,ACAM,SAM,最小表示法

  好了,基本就是这些吧。。代码还是贴一贴,为了一些还是不太理解的同学加(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了。。

先挖个大坑慢慢更新。。。