[Solution][Data Structure][Aho-Corasick Auto Machine][Dynamic Programming]JSOI2009 密码

【题目】

戳这里

【思路】

在Trie图上进行的状态压缩动态规划。

枚举长度0~L-1,每一次枚举所有节点的所有状态,对于所有转移,将当前的方法数转移到后继结点。

Dp的时间复杂度为.

对于输出方案的时候直接从答案状态反向DFS,将得到的字符串存在set中直接输出。具体见代码。

【代码】

/**************************************************************
    Problem: 1559
    User: wyfcyx
    Language: C++
    Result: Accepted
    Time:352 ms
    Memory:22300 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<string>
#include<iostream>
using namespace std;
int L , n;
char s[10];
int ch[101][26] , f[101] , st[101] , ind;
long long dp[101][26][1024];
queue<int> q;
set<string> S;
int last[26];
string sout;
void dfs(int len , int ord , int state)
{
    register int i , j , k;
    if (len == 0)
    {
        sout = "";
        for(i = 1 ; i <= L ; ++i)
            sout += ('a' + last[i]);
        S.insert(sout);
        return;
    }
    for(i = 0 ; i <= ind ; ++i)
    {
        for(j = 0 ; j < 26 ; ++j)
        {
            if (ch[i][j] != ord)
                continue;
            for(k = 0 ; k < (1 << n) ; ++k)
            {
                if (!dp[i][len - 1][k])
                    continue;
                if ((k | st[ord]) != state)
                    continue;
                last[len] = j;
                dfs(len - 1 , i , k);
            }
        }
    }
}
int main()
{
    scanf("%d%d" , &L , &n);
    register int i , j , k , l , tmp;
    int len;
    for(i = 1 ; i <= n ; ++i)
    {
        scanf("%s" , s);
        len = strlen(s);
        tmp = 0;
        for(j = 0 ; j < len ; ++j)
        {
            if (!ch[tmp][s[j] - 'a'])
                ch[tmp][s[j] - 'a'] = ++ind;
            tmp = ch[tmp][s[j] - 'a'];
        }
        st[tmp] |= 1 << (i - 1);
    }
    for(i = 0 ; i < 26 ; ++i)
    {
        if (ch[0][i])
            q.push(ch[0][i]);
    }
    //q.push(0);
    int u , v , r;
    while(!q.empty())
    {
        r = q.front();
        q.pop();
        for(i = 0 ; i < 26 ; ++i)
        {
            u = ch[r][i];
            if (!u)
            {
                v = f[r];
                while(v && !ch[v][i])
                    v = f[v];
                ch[r][i] = ch[v][i];
                continue;
            }
            q.push(u);
            v = f[r];
            while(v && !ch[v][i])
                v = f[v];
            f[u] = ch[v][i];
            st[u] |= st[f[u]];
           // st[u] |= st[r];
        }
    }
    dp[0][0][0] = 1;
    for(i = 0 ; i < L ; ++i)
    {
        for(j = 0 ; j <= ind ; ++j)
        {
            for(k = 0 ; k < (1 << n) ; ++k)
            {
                if (!dp[j][i][k])
                    continue;
                for(l = 0 ; l < 26 ; ++l)
                {
                    //if (!ch[j][l])
                        //continue;
                    dp[ch[j][l]][i + 1][k | st[ch[j][l]]] += dp[j][i][k];
                }
            }
        }
    }
    long long ans = 0;
    for(i = 0 ; i <= ind ; ++i)
        ans += dp[i][L][(1 << n) - 1];
    printf("%lld\n" , ans);
    if (ans <= 42)
    {
        for(i = 0 ; i <= ind ; ++i)
        {
            if (dp[i][L][(1 << n) - 1])
                dfs(L , i , (1 << n) - 1);
        }
        set<string>::iterator it;
        for(it = S.begin() ; it != S.end() ; ++it)
            cout << *it << endl;
    }
    return 0;
}
comments powered by Disqus