NFLS-DAY 2

Posted on By 张, 高畅

T0

今天和DALAO们学习了AC自动机。
其实就是Trie树+KMP，但是想想我昨天调了一个半小时的Trie树，今天的我瑟瑟发抖

T1

现在给出个关键词，和一个字符串文章，求字符串中出现的关键词

板子题，LUOGU的数据会更强一些

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,M=5e6+5;
int fail[M],cnt[M],tr[N][30],idx;
void insert(char *s)
{
    int len=strlen(s+1),p=0;
    for(int i=1;i<=len;i++)
    {
        int ch=s[i]-'a';
        if(!tr[p][ch])
        {
            tr[p][ch]=++idx;
            cnt[idx]=0;
        }
        p=tr[p][ch];
    }
    cnt[p]++;
}
void build()
{
    queue<int>q;
    for(int i=0;i<26;i++)
    {
        if(tr[0][i])q.push(tr[0][i]);
    }
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            if(tr[u][i])
            {
                fail[tr[u][i]]=tr[fail[u]][i];
                q.push(tr[u][i]);
            }
            else tr[u][i]=tr[fail[u]][i];
        }
    }
}
int clac(int u)
{
    int res=0;
    while(u&&~cnt[u])
    {
        res+=cnt[u];
        cnt[u]=-1;
        u=fail[u];
    }
    return res;
}
int get_res(char *s)
{
    int len=strlen(s+1),p=0,res=0;
    for(int i=1;i<=len;i++)
    {
        int ch=s[i]-'a';
        p=tr[p][ch];
        res+=clac(p);
    }
    return res;
}
char str[M];
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",str+1);
        insert(str);        
    }
    build();
    scanf("%s",str+1);
    printf("%d",get_res(str));
    return 0;
}

T2

JSOI 交给队员 ZYX 一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是 GW 文本生成器 v6 版。
该软件可以随机生成一些文章——总是生成一篇长度固定且完全随机的文章。 也就是说，生成的文章中每个字符都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章 s 包含单词 t，当且仅当单词 t 是文章 s 的子串）。但是，即使按照这样的标准，使用者现在使用的 GW 文本生成器 v6 版所生成的文章也是几乎完全不可读的。ZYX 需要指出 GW 文本生成器 v6 生成的所有文本中，可读文本的数量，以便能够成功获得 v7 更新版。你能帮助他吗？
答案对 1e4+7 取模（LUOGU链接）

反向考虑，答案就是总方案减去不带那些串的答案，因此考虑DP

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=6e3+10,mod=10007;
char s[N];
int n,m,f[N][M],ans=1,temp,idx,hh,tt,tr[M][30],ne[M],q[M],st[M];
void insert()
{
    int p=0;
    for(int i=0;s[i];i++)
    {
        int t=s[i]-'A';
        if(!tr[p][t])tr[p][t]=++idx;
        p=tr[p][t];
    }
    st[p]=1;
}
void build()
{
    hh=0;
    tt=-1;
    for(int i=0;i<26;i++)
    {
        if(tr[0][i])
        {
            ne[tr[0][i]]=0;
            q[++tt]=tr[0][i];
        }
    }
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=0;i<26;i++)
        {
            int j=tr[t][i];
            if(!j)tr[t][i]=tr[ne[t]][i];
            else
            {
                st[j]|=st[tr[ne[t]][i]];
                ne[j]=tr[ne[t]][i];
                q[++tt]=j;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%s",s);
        insert();
    }
    build();
    f[0][0]=1;
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<=idx;j++)
        {
            for(int k=0;k<26;k++)
            {
                if(!st[tr[j][k]])
                {
                    f[i][tr[j][k]]=(f[i][tr[j][k]]+f[i-1][j])%mod;
                }
            }
        }
    }
    for(int i=1;i<=m;i++)ans=(ans*26)%mod;
    for(int i=0;i<=idx;i++)temp=(temp+f[m][i])%mod;
    printf("%d",(ans-temp+mod)%mod);
    return 0;
}

T3

给出n个单词和一个整数m，单词只包含’A’,’B’,’C’，要求生成一个长度为m的串，使得这n个单词在串中出现的总次数最大，求最大出现次数(LUOGU链接，SPOJ原题，未绑定账号可能无法返回正确结果)

AC自动机（类似版子），DP求出现次数

#include<bits/stdc++.h>
using namespace std;
const int N=15,M=15005;
char s[N];
int n,m,f[1005][M],ans=1,idx,hh,tt,tr[M][30],ne[M],q[M],cnt[M];
void insert()
{
    int p=0;
    for(int i=0;s[i];i++)
    {
        int t=s[i]-'A';
        if(!tr[p][t])tr[p][t]=++idx;
        p=tr[p][t];
    }
    cnt[p]++;
}
void build()
{
    hh=0;
    tt=-1;
    for(int i=0;i<3;i++)
    {
        if(tr[0][i])
        {
            ne[tr[0][i]]=0;
            q[++tt]=tr[0][i];
        }
    }
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=0;i<3;i++)
        {
            int j=tr[t][i];
            if(!j)tr[t][i]=tr[ne[t]][i];
            else
            {
                ne[j]=tr[ne[t]][i];
                q[++tt]=j;
            }
        }
        cnt[t]+=cnt[ne[t]];
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    while(n--)
    {
        scanf("%s",s);
        insert();
    }
    build();
    memset(f,-0x3f,sizeof f);
    for(int i=0;i<=m;i++)f[i][0]=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<=idx;j++)
        {
            for(int k=0;k<3;k++)f[i][tr[j][k]]=max(f[i][tr[j][k]],f[i-1][j]+cnt[tr[j][k]]);
        }
    }
    int res=-0x3f3f3f3f;
    for(int i=0;i<=idx;i++)res=max(res,f[m][i]);
    printf("%d",res);
    return 0;
}

T4

给定 N 个字符串(S1,S2,…,Sn) ，要求找到一个最短的字符串 T，使得这 N 个字符串 (S1,S2,…,Sn) 都是 T 的子串。

状压DP+AC自动机

#include<bits/stdc++.h>
using namespace std;
const int N=605;
char s[N];
int n,st[N*25][9005],idx,hh,tt,tr[N*25][30],ne[N*25],q[N*25],state[N*25],cnt[N*25];
pair<int,int>Q[N*4200];
void insert(char *s,int T)
{
    int p=0;
    for(int i=0;s[i];i++)
    {
        int t=s[i]-'A';
        if(!tr[p][t])tr[p][t]=++idx;
        p=tr[p][t];
    }
    state[p]|=1<<(T-1);
}
void build()
{
    hh=0;
    tt=-1;
    for(int i=0;i<26;i++)
    {
        if(tr[0][i])
        {
            ne[tr[0][i]]=0;
            q[++tt]=tr[0][i];
        }
    }
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=0;i<26;i++)
        {
            int j=tr[t][i];
            if(!j)tr[t][i]=tr[ne[t]][i];
            else
            {
                ne[j]=tr[ne[t]][i];
                state[tr[t][i]]|=state[tr[ne[t]][i]];
                q[++tt]=j;
            }
        }
        cnt[t]+=cnt[ne[t]];
    }
}
vector<int>res;
int ans[N*4200],par[N*4200];
int main()
{
    int cnt=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s);
        insert(s,i);
    }
    build();
    hh=0;
    tt=-1;
    Q[++tt]={0,0};
    st[0][0]=1;
    int T=0;
    while(hh<=tt)
    {
        pair<int,int>u=Q[hh++];
        int p=u.first,s=u.second;
        if(s==((1<<n)-1))
        {
            while(T)
            {
                res.push_back(ans[T]);
                T=par[T];
            }
            for(int i=res.size()-1;~i;i--)printf("%c",res[i]+'A');
            return 0;
        }
        for(int i=0;i<26;i++)
        {
            if(!st[tr[p][i]][s|state[tr[p][i]]])
            {
                st[tr[p][i]][s|state[tr[p][i]]]=1;
                Q[++tt]={tr[p][i],s|state[tr[p][i]]};
                par[++cnt]=T;
                ans[cnt]=i;
            } 
        }
        T++;
    }
    return 0;
}

T5

对于一个 10 位的密码以及观察到的字符串 hello 与 world，可能的密码组合为 helloworld与 worldhello；而对于 6 位的密码以及到的字符串 good 与 day,可能的密码组合为 gooday。
有了这些信息，就能够大大地减少尝试的次数了。请编一个程序，计算所有密码组合的可能。密码中仅可能包含 a-z 之间的小写字母

AC自动机+DP+DFS
DFS用于搜索方案，由于方案数量<=42，因此可以直接爆搜

#include<bits/stdc++.h>
using namespace std;
const int N=12,M=105,C=26;
typedef long long LL;
int m,n,acsize,valsize,c[M],e[N],val[M],S;
LL res,f[C][M][1030];
struct AC
{
    int tr[M][C],ne[M];
    queue<int>q;
    void insert(char *s,int T)
    {
        int p=0,len=strlen(s+1);
        for(int i=1;i<=len;i++)
        {
            int ch=s[i]-'a';
            if(!tr[p][ch])tr[p][ch]=++acsize;
            p=tr[p][ch];
            c[p]=ch;
        }
        e[T]=p;
        val[p]=1;
    }
    void build()
    {
        int p=0;
        for(int i=0;i<C;i++)
        {
            if(tr[0][i])q.push(tr[0][i]);
        }
        while(q.size())
        {
            int u=q.front();
            q.pop();
            for(int i=0;i<C;i++)
            {
                if(tr[u][i])
                {
                    ne[tr[u][i]]=tr[ne[u]][i];
                    q.push(tr[u][i]);
                }
                else tr[u][i]=tr[ne[u]][i];
            }
        }
        for(int i=0;i<=acsize;i++)val[ne[i]]=0;
        for(int i=0;i<=acsize;i++)
        {
            if(val[i])
            {
                val[i]=(1<<valsize);
                valsize++;
            }
        }
        S=(1<<valsize)-1;
    }
    void DP()
    {
        f[0][0][0]=1;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<=acsize;j++)
            {
                for(int k=0;k<=S;k++)
                {
                    for(int t=0;t<C;t++)f[i+1][tr[j][t]][k|val[tr[j][t]]]+=f[i][j][k];
                }
            }
        }
    }
}ac;
struct STRING
{
    char s[30];
    void print()
    {
        for(int i=1;i<=m;i++)printf("%c",s[i]);
        puts("");
    }
    friend bool operator <(STRING x,STRING y)
    {
        for(int i=1;i<=m;i++)
        {
            if(x.s[i]!=y.s[i])return x.s[i]>y.s[i];
        }
        return 0;
    }
}stk;
vector<STRING>str;
void dfs(int x,int u,int y,int z)
{
    stk.s[x]=z+'a';
    if(x==1)
    {
        str.push_back(stk);
        return;
    }
    for(int i=0;i<=acsize;i++)
    {
        if(f[x-1][i][y]>0&&ac.tr[i][z]==u)dfs(x-1,i,y,c[i]);
    }
    if(val[u])
    {
        for(int i=0;i<=acsize;i++)
        {
            if(f[x-1][i][y^val[u]]>0&&ac.tr[i][z]==u)dfs(x-1,i,y^val[u],c[i]);
        }   
    }
}
char ss[N];
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",ss+1);
        ac.insert(ss,i);
    }
    ac.build();
    ac.DP();
    for(int i=0;i<=acsize;i++)res+=f[m][i][S];
    printf("%lld\n",res);
    if(res>42)return 0;
    for(int i=0;i<=acsize;i++)
    {
        if(f[m][i][S])dfs(m,i,S,c[i]);
    }
    sort(str.begin(),str.end());
    while(!str.empty())
    {
        (str.back()).print();
        str.pop_back();
    }
    return 0;
}
训练日志