關于KMP算法

首先來個闆子

Luogu P3375 

注意字元串要從1開始哦

其實kmp的精髓（自己口胡）就是轉移

我們已經知道目前i的next

那麼将i右移一位後，我們隻要比較目前位和之前的next是否相等即可（next遞歸下去）

而每次next最多增加1，複雜度就可以保證了

#include<cstdio>  
#include<cstring>  
const int N=1000000+7;  
char a[N],b[N];  
int lena,lenb;  
int next[N];  
void init()  
{  
    next[1]=0;  
    int j=0;  
    for(int i=2;i<=lenb;i++)  
    {  
        while(j&&b[j+1]!=b[i])  j=next[j];  
        if(b[j+1]==b[i])    j++;  
        next[i]=j;  
    }  
}  
void match()  
{  
    int j=0;  
    for(int i=1;i<=lena;i++)  
    {  
        while(j&&b[j+1]!=a[i])  j=next[j];  
        if(b[j+1]==a[i])    j++;  
        if(j==lenb) printf("%d\n",i-lenb+1);//如果比對成功了，那麼next就會跳到前面繼續比較下一個   
    }     
}  
int main()  
{  
    scanf("%s %s",a+1,b+1);  
    lena=strlen(a+1);  
    lenb=strlen(b+1);  
//  printf("%d %d\n",lena,lenb);  
    init();  
    match();  
    for(int i=1;i<=lenb;i++) printf("%d ",next[i]);  
    printf("\n");  
    return 0;  
}  
           

關于next樹：

把每個next[i]看成fa[i]

那麼我們就可以得到一顆以0為根的樹

例題：

1、51nod 1277

那麼我們直接從樹的底部往上傳資訊（在本題中直接從n~1枚舉即可）然後統計一下答案就可以了

2、bzoj3670: [Noi2014]動物園

最暴力的方法就是從next[i]一直next下去

直到為0，然後統計ans

然而我們可以統計每一個點在next樹上的深度dep

那麼我們隻要找出第一個j，其中2*j<=i，它的dep就是num[i]了

考慮我們怎麼求出每個i的第一個j

發現這個東西類似next數組，是可以轉移的

将i右移一位後，它指向的j也最多隻能+1

是以我們隻用掃一遍就可以了

核心代碼：（next，dep已經處理好了）

long long ans=1;
j=0;
for(int i=2;i<=n;i++)
{
	while(j&&a[j+1]!=a[i])	j=next[j];
	if(a[j+1]==a[i])	j++;
	while(j&&(j<<1)>i)	j=next[j];
	ans=ans*(dep[j]+1)%mod;	
}