XCPC Notes

Appearance

发布时间：2024-07-28

AC自动机 ​

模板(简单版) ​

cpp
int tr[N][26],cnt[N],idx;
int ne[N];
bool vis[N];
void insert(string &s){
    int p=0;
    for(int i=0;i<s.size();i++){
        int v=s[i]-'a';
        if(!tr[p][v])tr[p][v]=++idx;
        p=tr[p][v];
    }
    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.empty()){
        auto u=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            int c=tr[u][i];
            if(!c)continue;
            int j=ne[u];
            while(j&&!tr[j][i])j=ne[j];
            if(tr[j][i])j=tr[j][i];
            ne[c]=j;
            q.push(c);
        }
    }
}
int query(string &s){
    int ans=0;
    map<int,bool> mp;
    for(int i=0,j=0;i<s.size();i++){
        int v=s[i]-'a';
        while(j&&!tr[j][v])j=ne[j];
        if(tr[j][v])j=tr[j][v];
        int p=j;
        while(p&&!vis[p]){
            ans+=cnt[p];
            vis[p]=1;
            p=ne[p];
        }
    }
    return ans;
}

模板(改进版) ​

cpp
int tr[N][26],cnt[N],ne[N],idx;
bool vis[N];
void insert(string &s){
    int p=0;
    for(int i=0;i<s.size();i++){
        int v=s[i]-'a';
        if(!tr[p][v])tr[p][v]=++idx;
        p=tr[p][v];
    }
    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.empty()){
        auto u=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            int &p=tr[u][i];
            if(!p)p=tr[ne[u]][i];
            else{
                ne[p]=tr[ne[u]][i];
                q.push(p);
            }
        }
    }
}
int query(string &s){
    int ans=0;
    for(int i=0,j=0;i<s.size();i++){
        int v=s[i]-'a';
        j=tr[j][v];
        int p=j;
        while(p&&!vis[p]){
            ans+=cnt[p];
            vis[p]=1;
            p=ne[p];
        }
    }
    return ans;
}

AC自动机与拓扑优化 ​

cpp
int tr[N][26],cnt[N],idx,id[N],ne[N],din[N];
void insert(string &s,int pos){
    int p=0;
    for(int i=0;i<s.size();i++){
        int v=s[i]-'a';
        if(!tr[p][v])tr[p][v]=++idx;
        p=tr[p][v];
    }
    id[pos]=p;
}
void build(){
    queue<int> q;
    for(int i=0;i<26;i++){
        if(tr[0][i])q.push(tr[0][i]);
    }
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            int &p=tr[u][i];
            if(!p)p=tr[ne[u]][i];
            else{
                ne[p]=tr[ne[u]][i];
                din[ne[p]]++;
                q.push(p);
            }
        }
    }
}
void query(string &s){
    for(int i=0,j=0;i<s.size();i++){
        int v=s[i]-'a';
        j=tr[j][v];
        cnt[j]++;
    }
}
void topu(){
    queue<int> q;
    for(int i=0;i<=idx;i++){
        if(din[i]==0)q.push(i);
    }
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        int v=ne[u];
        cnt[v]+=cnt[u];
        if(--din[v]==0)q.push(v);
    }
}
void solve(){
    int n;
    cin>>n;
    string s;
    for(int i=0;i<n;i++){
        cin>>s;
        insert(s,i);
    }
    build();
    cin>>s;
    query(s);
    topu();
    for(int i=0;i<n;i++)cout<<cnt[id[i]]<<"\n";
}

修复DNA(AC自动机+dp) ​

题意：
给定一个DNA序列，和若干串病毒DNA片段，问至少需要修改多少次，使得DNA序列不含病毒串
思路：

  • 将DNA病毒串建立ac自动机，然后ac自动机dp
  • 注意点:cnt[p]+=cnt[ne[p]]
cpp
int tr[N][4],cnt[N],ne[N],idx;
int f[N][N];
int get(char c){
    if(c=='A')return 0;
    if(c=='G')return 1;
    if(c=='C')return 2;
    return 3;
}
void insert(string &s){
    int p=0;
    for(int i=0;i<s.size();i++){
        int v=get(s[i]);
        if(!tr[p][v])tr[p][v]=++idx;
        p=tr[p][v];
    }
    cnt[p]++;
}
void build(){
    queue<int> q;
    for(int i=0;i<4;i++){
        if(tr[0][i])q.push(tr[0][i]);
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int &p=tr[u][i];
            if(!p)tr[u][i]=tr[ne[u]][i];
            else{
                ne[p]=tr[ne[u]][i];
                q.push(p);
                cnt[p]+=cnt[ne[p]];
            }
        }
    }
}
void solve(){
    int t=1,n;
    while(cin>>n,n){
        memset(tr,0,sizeof tr);
        memset(cnt,0,sizeof cnt);
        memset(ne,0,sizeof ne);
        idx=0;
        string s;
        for(int i=0;i<n;i++){
            cin>>s;
            insert(s);
        }
        build();
        cin>>s;
        memset(f,0x3f,sizeof f);
        f[0][0]=0;
        int m=s.size();
        for(int i=0;i<m;i++){
            for(int j=0;j<=idx;j++){
                for(int k=0;k<4;k++){
                    int t=get(s[i])!=k;
                    int p=tr[j][k];
                    if(!cnt[p])f[i+1][p]=min(f[i+1][p],f[i][j]+t);
                }
            }
        }
        int res=1e9;
        for(int i=0;i<=idx;i++)res=min(res,f[m][i]);
        cout<<"Case "<<t++<<": ";
        if(res!=1e9)cout<<res<<"\n";
        else cout<<"-1\n";
    }
}

P2292 [HNOI2004] L 语言(拓扑排序变化) ​

题意：
给多个单词，多个文本串，对于每个文本串，问能识别的最大长度
思路：

  • 建立ac自动机
  • dp方程转移：fi∣=fjf_i|=f_j，在ac自动机上匹配即可
  • 但是这样写会tle，原因在于查询时fail指针的跳回，需要找到方法O(1)查询
  • 发现每个单词的长度最大为20，因此可以状态压缩
  • 第i个1表示当前拥有长度为i的后缀
  • 在匹配时，只需要与当前指针的状态相与，即可发现是否能跳
cpp
int tr[N][26],cnt[N],idx,ne[N],dep[N],state[N];
void insert(string &s){
    int p=0;
    for(int i=0;i<s.size();i++){
        int v=s[i]-'a';
        if(!tr[p][v])tr[p][v]=++idx;
        p=tr[p][v];
    }
    cnt[p]++;
}
void build(){
    queue<int> q;
    for(int i=0;i<26;i++){
        if(tr[0][i])q.push(tr[0][i]),dep[tr[0][i]]=1;
    }
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        state[u]=state[ne[u]];
        if(cnt[u])state[u]|=1<<dep[u];
        for(int i=0;i<26;i++){
            int &p=tr[u][i];
            if(!p)p=tr[ne[u]][i];
            else{
                ne[p]=tr[ne[u]][i];
                dep[p]=dep[u]+1;
                q.push(p);
            }
        }
    }
}
void solve(){
    int n,m;
    string s;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s;
        insert(s);
    }
    build();
    while(m--){
        cin>>s;
        int n=s.size();
        int ans=0;
        int st=1;
        for(int i=1,j=1;i<=n;i++){
            int v=s[i-1]-'a';
            j=tr[j][v];
            st<<=1;
            if(state[j]&st)ans=max(ans,i),st|=1;
        }
        cout<<ans<<"\n";
    }
}

P4045 [JSOI2009] 密码(AC自动机+状压dp) ​

题意：
给定n个字符串和一个长度L，构造文本串L，满足所有字符串均在文本串中出现
如果个数不超过42个就输出
1≤n≤10,1≤L≤251 \leq n \leq 10 ,1 \leq L \leq 25
思路：

  • 最多只有10个字符串，状压dp+AC自动机
  • fi,j,k表示前i个长度，当前匹配到ac自动机的j节点，包含状态k个字符串的个数f_{i,j,k} 表示前i个长度，当前匹配到ac自动机的j节点，包含状态k个字符串的个数
  • 时间复杂度： O(L∑∣s∣⋅2k⋅26)O(L \sum |s| \cdot 2^k \cdot 26)
  • 难点在于方案输出，首先要预处理当前状态是否能走到最终状态，然后爆搜即可
cpp
int tr[N][26],idx,ne[N],state[N];
int f[30][200][1<<10];
int g[30][200][1<<10];
void insert(string &s,int pos){
    int p=0;
    for(int i=0;i<s.size();i++){
        int v=s[i]-'a';
        if(!tr[p][v])tr[p][v]=++idx;
        p=tr[p][v];
    }
    state[p]|=1<<pos;
}
void build(){
    queue<int> q;
    for(int i=0;i<26;i++){
        if(tr[0][i])q.push(tr[0][i]);
    }
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        state[u]|=state[ne[u]];
        for(int i=0;i<26;i++){
            int &p=tr[u][i];
            if(!p)p=tr[ne[u]][i];
            else{
                ne[p]=tr[ne[u]][i];
                q.push(p);
            }
        }
    }
}
int n,m;
int ans[30];
int dfs(int x,int y,int z){
    if(x==n){
        return g[x][y][z]=(z==(1<<m)-1);
    }
    if(~g[x][y][z])return g[x][y][z];
    int flag=0;
    for(int i=0;i<26;i++){
        int p=tr[y][i];
        flag|=dfs(x+1,p,z|state[p]);
    }
    return g[x][y][z]=flag;
}
void output(int x,int y,int z){
    if(!g[x][y][z])return;
    if(x==n){
        for(int i=1;i<=n;i++){
            cout<<(char)(ans[i]+'a');
        }
        cout<<"\n";
        return;
    }
    for(int i=0;i<26;i++){
        int p=tr[y][i];
        ans[x+1]=i;
        output(x+1,p,z|state[p]);
    }
}
void solve(){
    cin>>n>>m;
    string s;
    for(int i=0;i<m;i++){
        cin>>s;
        insert(s,i);
    }
    build();
    f[0][0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=idx;j++){
            for(int mask=0;mask<1<<m;mask++){
                for(int k=0;k<26;k++){
                    int p=tr[j][k];
                    f[i+1][p][mask|state[p]]+=f[i][j][mask];
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<=idx;i++)ans+=f[n][i][(1<<m)-1];
    cout<<ans<<"\n";
    if(ans>42)return;
    memset(g,-1,sizeof g);
    dfs(0,0,0);
    output(0,0,0);
}

P4052 [JSOI2007] 文本生成器(AC自动机+dp) ​

题意：
给定多个字符串，生成文本串满足至少存在一个字符串，求个数
思路：

  • fi,j,0/1表示枚举到i，ac自动机的j，是否出现过字符串的方案数f_{i,j,0/1} 表示枚举到i，ac自动机的j，是否出现过字符串的方案数
  • ans=∑fm,i,1ans= \sum f_{m,i,1}
cpp
int tr[N][26],idx,ne[N],cnt[N];
int f[110][N][2];
void insert(string &s){
    int p=0;
    for(int i=0;i<s.size();i++){
        int v=s[i]-'A';
        if(!tr[p][v])tr[p][v]=++idx;
        p=tr[p][v];
    }
    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.empty()){
        auto u=q.front();
        q.pop();
        cnt[u]+=cnt[ne[u]];
        for(int i=0;i<26;i++){
            int &p=tr[u][i];
            if(!p)p=tr[ne[u]][i];
            else{
                ne[p]=tr[ne[u]][i];
                q.push(p);
            }
        }
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    string s;
    for(int i=1;i<=n;i++){
        cin>>s;
        insert(s);
    }
    build();
    f[0][0][0]=1;
    for(int i=0;i<m;i++){
        for(int j=0;j<=idx;j++){
            for(int k=0;k<26;k++){
                int p=tr[j][k];
                int g=(cnt[p]>0);
                for(int x=0;x<2;x++){
                    f[i+1][p][x|g]+=f[i][j][x];
                    f[i+1][p][x|g]%=mod;
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<=idx;i++){
        ans+=f[m][i][1];
        ans%=mod;
    }
    cout<<ans<<"\n";
}

Wenwei Lin · 2022 — 2025