AC自动机:

P5357 【模板】AC自动机(二次加强版)

·不要像以前一样习惯性把trie树的根设为1,从0开始的话后面getfail比较方便。

·trie树的节点编号是无序的,统计答案需要dfs或者拓扑,按编号循环显然是错的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int S=2e6+10,N=2e5+10;
int n,cnt[N],now,tot,len,tree[N][27],ed[N],num[N],fail[N];
char s[S];
int head[N],Next[N],tot1,ver[N],du[N];
void add(int x,int y){
    ver[++tot1]=y;
    Next[tot1]=head[x];
    head[x]=tot1;
}
void insert(int x){
    now=0;
    len=strlen(s+1);
    for(int i=1;i<=len;i++){
        if(!tree[now][s[i]-'a'])tree[now][s[i]-'a']=++tot;
        now=tree[now][s[i]-'a'];
    }
    ed[now]=1;
    cnt[x]=now;
}
queue<int>q;
void getfail(){
    for(int i=0;i<26;i++){
        if(tree[0][i]){
            fail[tree[0][i]]=0;
            q.push(tree[0][i]);
            add(tree[0][i],0);
            du[0]++;
        }
    }
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            int v=tree[u][i];
            if(v){
                fail[v]=tree[fail[u]][i];
                q.push(v);
                add(v,fail[v]);
                du[fail[v]]++;
            }
            else{
                tree[u][i]=tree[fail[u]][i];
            }
        }
    }
}
void AC(){
    now=0;
    len=strlen(s+1);
    for(int i=1;i<=len;i++){
        int v=tree[now][s[i]-'a'];
        num[v]++;
        now=v;
    }
}
int main()
{
//    freopen("1.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        insert(i);
    }
    getfail();
    scanf("%s",s+1);
    AC();
    for(int i=1;i<=tot;i++){
        if(!du[i])q.push(i);
    }
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=Next[i]){
            int y=ver[i];
            num[y]+=num[u];
            du[y]--;
            if(!du[y])q.push(y);
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d\n",num[cnt[i]]);
    }
    return 0;
}
/*
6
a
bb
aa
abaa
abaaa
abaaa
abaaabaa
*/
P5357 【模板】AC自动机(二次加强版)

P2444 [POI2000]病毒

·跳fail能跳到危险节点的节点,自身必为危险节点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,now,tot,len,flag;
char s[30010];
int tree[30010][2],ed[30010],fail[30010];
void insert(){
    now=0;
    len=strlen(s+1);
    for(int i=1;i<=len;i++){
        if(!tree[now][s[i]-'0'])tree[now][s[i]-'0']=++tot;
        now=tree[now][s[i]-'0'];
    }
    ed[now]=1;
}
queue<int>q;
void getfail(){
    for(int i=0;i<2;i++){
        fail[tree[0][i]]=0;
        if(tree[0][i]){
            q.push(tree[0][i]);
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<2;i++){
            int v=tree[u][i];
            if(v){
                fail[v]=tree[fail[u]][i];
                if(ed[fail[v]])ed[v]=1;
                q.push(v);
            }
            else tree[u][i]=tree[fail[u]][i];
        }
    }
}
int vis[30010];
int dfs(int x){
    if(flag)return 1;
    if(ed[x])return 0;
    if(vis[x])return 1;
    if(x)vis[x]=1;
    int val=(dfs(tree[x][0])|dfs(tree[x][1]));
    if(val)flag=1;
    vis[x]=0;
    return val;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        insert();
    }
    getfail();
    if(dfs(0))printf("TAK\n");
    else printf("NIE\n");
    return 0;
}
/*
3
011
11
00000
*/
P2444 [POI2000]病毒

P4052 [JSOI2007]文本生成器

·trie树里很多走不到的字母相当于回到根,转移和统计带根一起算

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
char s[110];
int now,len,tot,tree[6010][26],fail[6010],ed[6010];
void insert(){
    now=0;
    len=strlen(s+1);
    for(int i=1;i<=len;i++){
        if(!tree[now][s[i]-'A'])tree[now][s[i]-'A']=++tot;
        now=tree[now][s[i]-'A'];
    }
    ed[now]=1;
}
queue<int>q;
void getfail(){
    for(int i=0;i<26;i++){
        if(tree[0][i]){
            q.push(tree[0][i]);
        }
    }
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            int v=tree[u][i];
            if(v){
                fail[v]=tree[fail[u]][i];
                q.push(v);
                if(ed[fail[v]])ed[v]=1;
            }
            else{
                tree[u][i]=tree[fail[u]][i];
            }
        }
    }
}
int f[110][6010],ans;
void work(){
    f[0][0]=1;
    for(int t=0;t<m;t++){
        for(int i=0;i<=tot;i++){
            if(ed[i])continue;
            for(int j=0;j<26;j++){
                if(ed[tree[i][j]])continue;
                f[t+1][tree[i][j]]=(f[t+1][tree[i][j]]+f[t][i])%10007;
            }
        }
    }
    for(int i=0;i<=tot;i++)ans=(ans+f[m][i])%10007;
}
int ks(int x,int k){
    int num=1;
    while(k){
        if(k&1)num=num*x%10007;
        x=x*x%10007;
        k>>=1;
    }
    return num;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        insert();
    }
    getfail();
    work();
    printf("%d\n",((ks(26,m)-ans)%10007+10007)%10007);
    return 0;
}
P4052 [JSOI2007]文本生成器

回文自动机:

(前置)P3805 【模板】manacher算法

·注意细节

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[23000010],a[11000010];
int len,lst=0,p[23000010],pos,ans;
void manacher(){
    for(int i=1;i<=len*2+1;i++){
        if(lst<i){
            pos=i;
            for(int j=i;j<=len*2+1&&2*i-j>0;j++){
                if(s[j]!=s[2*i-j])break;
                p[i]++;
                lst=j;
            }
        }
        else{
            int v=2*pos-i;
            if(i+p[v]-1>lst)p[i]=lst-i+1;
            else if(i+p[v]-1<lst)p[i]=p[v];
            else{
                p[i]=p[v];
                while(s[i+p[i]]==s[i-p[i]])p[i]++;
                lst=i+p[i]-1;
                pos=i;
            }
        }
    }
}
int main()
{
    scanf("%s",a+1);
    len=strlen(a+1);
    s[0]=s[1]='#';
    for(int i=1;i<=len;i++){
        s[i*2]=a[i];
        s[i*2+1]='#';
    }
    manacher();
    for(int i=1;i<=2*len+1;i++)ans=max(ans,p[i]-1);
    printf("%d\n",ans);
    return 0;
}
P3805 【模板】manacher算法
12-25 18:11