UVA - 1076 || LA 4126 Password Suspects （AC自动机 + 状压DP + 打印解）

77 阅读 0 评论 51 点赞

我是靠谱客的博主苗条小笼包，最近开发中收集的这篇文章主要介绍UVA - 1076 || LA 4126 Password Suspects （AC自动机 + 状压DP + 打印解），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

让你构造一个长度为n 的串，告诉你m个串，要求长度为n 的串必须包含m 个串，问你有多少种方案。如果方案数 <= 42 输出所有解。

思路：

不看输出方案。

很明显一个自动机 + 状压的题目。

令dp[i][j][k] 表示构造字符串的第i 位，目前在自动机的j 结点，包含m 个串的状态为k 的方案数。那么直接转移就好了。

但是要打印解。

感觉这里比较乱想了好久。

因为自己写的dp 都是正着推的，从dp[0][0][0] 推到终点。但是这样不好打印解。

于是改成了记忆话搜索，从终点向前推。

这样直接从起点在dfs 一遍就能打印解了，直接看当前的dp 值是不是大于0 即可，大于0 就继续递归，否则return。

注意：

可能会有重复单词的出现。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
using namespace std;

const int maxn = 100 + 2;

struct Trie{
    int L, root;
    int next[maxn][26];
    int fail[maxn];
    int flag[maxn];
    long long dp[26][maxn][ (1<<10)+2 ];

    void init(){
        L = 0;
        root = newnode();
    }

    int newnode(){
        for (int i = 0; i < 26; ++i){
            next[L][i] = -1;
        }
        flag[L] = 0;
        return L++;
    }


    void insert(char* s,int ii){
        int len = strlen(s);
        int nod = root;
        for (int i = 0; i < len; ++i){
            int id = s[i] - 'a';
            if (next[nod][id] == -1){
                next[nod][id] = newnode();
            }
            nod = next[nod][id];
        }
        flag[nod] = ii;
    }

    void bfs(){
        queue<int>q;

        fail[root] = root;

        for (int i = 0; i < 26; ++i){
            if (next[root][i] == -1){
                next[root][i] = root;
            }
            else {
                fail[next[root][i] ] = root;
                q.push(next[root][i]);
            }

        }


        while(!q.empty()){
            int u = q.front(); q.pop();
            flag[u] |= flag[fail[u] ];
            for (int i = 0; i < 26; ++i){
                if (next[u][i] == -1){
                    next[u][i] = next[fail[u] ][i];
                }
                else {
                    fail[next[u][i] ] = next[fail[u] ][i];
                    q.push(next[u][i]);
                }
            }
        }
    }

    vector<string>v;
    long long dfs(int i, int j, int k,int n,int m){
        long long& ans = dp[i][j][k];
        if (ans != -1) return ans;
        if (i == n){
            if (k == (1<<m) - 1){
                return ans = 1;
            }
            return ans = 0;
        }
        ans = 0;
        for (int l = 0; l < 26; ++l){
            int nx = next[j][l];
            char ch = 'a' + l;
            ans += dfs(i+1, nx, k | flag[nx],  n, m);
        }
        return ans;
    }

    void find(int i,int j,int k, string p, int n, int m){
        if (i >= n){
            if (k == (1<<m) - 1){
                v.push_back(p);
            }
            return;
        }
        if (dp[i][j][k] <= 0) return;

        for (int l = 0; l < 26; ++l){
            int nx = next[j][l];
            char ch = l + 'a';
            find(i+1, nx, k | flag[nx], p + ch, n, m);
        }

    }
    void solve(int n, int m){
        v.clear();
        memset(dp,-1,sizeof dp);
        long long ans = dfs(0,0,0,n, m);
        printf("%lld suspectsn", ans);
        if (ans <= 42){
            find(0,0,0,"", n, m);
            for (int i = 0; i < v.size(); ++i){
                printf("%sn", v[i].c_str());
            }
        }
    }
}ac;
/**
4 1
hee

**/

int n, m;
char s[11][maxn];
int state[11];
int main(){
    int ks = 0;
    while(~scanf("%d %d",&n, &m)){
        if (n == 0 && m == 0) break;
        ac.init();
        for (int i = 0; i < m; ++i){
            scanf("%s", s[i]);
            state[i] = 0;
        }
        for (int i = 0; i < m; ++i){
            for (int j = 0; j < m; ++j){
                if (!strcmp(s[i], s[j])){
                    state[i] |= (1<<j);
                }
            }
        }
        for (int i = 0; i < m; ++i){
            ac.insert(s[i], state[i]);
        }
        ac.bfs();
        printf("Case %d: ",++ks);
        ac.solve(n, m);
    }
    return 0;
}