kmp的next算循环节:

当满足i%(i-next[i])==0,则循环节长度为i-next[i]

p为s的循环节,|S|-p为一个border

next[i] s[1...i]的最长border:(算前缀和后缀相等的个数 border树 对前缀a找到一个<=b的最长border 用树上倍增

前缀等于后缀

b为a的border,c为b的border,则c为a的border

扩展kmp:

求lcp(s[i],s[1]),可求不超过1/2border,用半个前缀的i去找,min(l[i],i) l[i]=lcp(s[i],s[1]).

kmp板子:

#include<bits/stdc++.h>
#define maxs 1000005
using namespace std;
int n;
char s1[10005],s2[maxs];
int fail[10005];
void getfail(char *s){
    int len=strlen(s);
    int i=0,j=-1;
    fail[0]=-1;
    while(i<len){
        while(j>=0&&s[i]!=s[j]) j=fail[j];
        i++,j++;
        fail[i]=j;
    }
}
int kmp(char *s1,char *s2){
    int cnt=0,len1=strlen(s1),len2=strlen(s2);
    int i=0,j=0;
    while(i<len2){
        while(j>=0&&s1[j]!=s2[i]) j=fail[j];
        i++,j++;
        if(j==len1) cnt++,j=fail[j];
    }
    return cnt;
}
void init(){
    scanf("%s%s",s1,s2);
    getfail(s1);
    int ans=kmp(s1,s2);
    printf("%d\n",ans);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) init();
    
    return 0;
}

AC自动机板子:

#include<bits/stdc++.h>
#define maxn 40000
using namespace std;
char ss[100005];
char s[51];
struct node{
    int fail;
    int to[26];
    int calc;
    node(){
        fail=0;
        memset(to,0,sizeof(to));
        calc=0;
    }
}t[1000005];
int n,rt=1,np=1;
void insert(char *s){
    int root=rt;
    for(int i=0;s[i];i++){
        int d=s[i]-'a';
        if(!t[root].to[d]){
            np++;
            t[root].to[d]=np;
        }
        root=t[root].to[d];
    }
    t[root].calc++;
}
int q[1000005];
void makefail(){
    int front=0,rear=0;
    q[rear++]=rt;
    while(front!=rear){
        int i=q[front];front++;
        for(int j=0;j<=25;j++){
            if(t[i].to[j]){
                if(i==rt){
                    t[t[i].to[j]].fail=rt;
                }
                else{
                    int p=t[i].fail;
                    while(p){
                        if(t[p].to[j]){
                            t[t[i].to[j]].fail=t[p].to[j];
                            break;
                        }
                        p=t[p].fail;
                    }
                    if(p==0) t[t[i].to[j]].fail=rt;
                }
                q[rear++]=t[i].to[j];
            }
        }
    }
}
int query(char *s){//更改为zzq型
    int ans=0,cur=rt;
  for(int i=0;s[i];i++){
    int c=s[i]-'a',cur=t[cur].to[c];
    for(int f=cur;f!=rt;f=t[f].fail) ans+=t[f].calc,t[f].calc=0;
  }
  return ans;
}
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        insert(s);
    }
    scanf("%s",ss);
    makefail();
    int ans=query(ss);
    printf("%d",ans);
}
int main(){
    init();
    
    return 0;
}

fail树

http://www.cnblogs.com/zzqsblog/p/6227545.html

https://blog.csdn.net/txl199106/article/details/45315703

https://www.cnblogs.com/justPassBy/p/5412110.html

例题 bzoj2434 阿狸的打字机

https://www.cnblogs.com/zzqsblog/p/5560645.html

一个串有不超过n个本质不同的回文串

bitset维护字符串匹配:

时间复杂度(nm/32) 资瓷修改S(模板串

后缀树和fail树常用,做相关例题

简单的数学题最后推出的公式:

$\sum_{d=1}^n \phi(d)d^2 F(\lfloor\frac{n}{d}\rfloor)^2$

其中$F(i)=\sum_{i=1}^n i​$

Last modification:February 23rd, 2019 at 11:17 am