UVALive 4126 Password Suspects (AC自动机+DP)

59 阅读 0 评论 39 点赞

我是靠谱客的博主怕孤单百褶裙，最近开发中收集的这篇文章主要介绍UVALive 4126 Password Suspects (AC自动机+DP)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：https://vjudge.net/problem/UVALive-4126

题目大意：有一个长度为n的未知小写字母串，你已经知道了它的一些连续子串（但不知道出现位置，这些字串可能相互重叠）。比如，若长度为10，有两个连续子串hello和world，则只有两种可能：helloworld和worldhello。求可能的串的个数，若个数不超过42，按字典序输出所有串。

思路：将连续子串构造AC自动机。然后在自动机上进行DP，令dp(u, step, S)表示当前在结点u，已经走了step步（即已经造出了长度为step的串），包含的连续子串集合为S，接着往下构造的方案数，答案即为dp(0, 0, 0)。输出方案时同样按照DP方程的思路进行转移即可。

#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<iostream>
#include<set>
#include<map>
#include<cmath>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#define fin freopen("a.txt","r",stdin)
#define fout freopen("a.txt","w",stdout)
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int inf = 1e9 + 10;
const int maxnode = 105;
const int sigma_size = 26;
const int maxn = 5e4 + 10;
int Max;
char s[100];

LL dp[maxnode][maxnode][1<<10];
int n, m;

struct Tree
{
	int ch[maxnode][sigma_size];
	int f[maxnode];
	int val[maxnode];
	int last[maxnode];
	int sz;
	int idx(char c) { return c - 'a'; }

    void init() {
        memset(ch[0], 0, sizeof ch[0]);
        sz = 1;
    }

    void getFail() {
        queue<int> q;
        f[0] = 0;
        for(int c = 0; c < sigma_size; c++) {
        	int u = ch[0][c];
        	if(u) { f[u] = 0; q.push(u); last[u] = 0;}
        }
        while(!q.empty()) {
        	int r = q.front(); q.pop();
        	for(int c = 0; c < sigma_size; c++) {
        		int u = ch[r][c];
        		if(!u) { ch[r][c] = ch[f[r]][c]; continue; }
        		q.push(u);
        		int v = f[r];
        		while(v && !ch[v][c]) v = f[v];
        		f[u] = ch[v][c];
        		last[u] = val[f[u]] ? f[u] : last[f[u]];
        	}
        }
    }

    bool insert(char *s, int v) {
    	bool ok = false;
    	int n = strlen(s), u = 0;
    	for(int i = 0; i < n; i++) {
    		int c = idx(s[i]);
    		if(!ch[u][c]) {
    			memset(ch[sz], 0, sizeof ch[sz]);
    			val[sz] = 0;
    			ch[u][c] = sz++;
    			ok = true;
    		}
    		u = ch[u][c];
    	}
    	if(ok) val[u] = v;
    	return ok;
    }

    void print(int u, int& S)
    {
        if(u) {
            S |= (1<<(val[u]-1));
            print(last[u], S);
        }
    }

    LL DP(int u, int step, int S)
    {
        if(step == n) { return S == (1<<m)-1; }
        LL &ans = dp[u][step][S];
        if(ans >= 0) return ans;
        ans = 0;
        for(int i = 0; i < sigma_size; i++)
        {
            int v = ch[u][i];
            int S2 = S;
            if(val[v]) print(v, S2);
            else if(last[v]) print(last[v], S2);
            ans += DP(v, step+1, S2);
        }
        return ans;
    }

    void Out(int u, int step, int S, string s)
    {
    	if(step == n) { printf("%sn", s.c_str()); return ;}
        for(int i = 0; i < sigma_size; i++)
        {
        	int v = ch[u][i];
        	int S2 = S;
        	if(val[v]) print(v, S2);
        	else if(last[v]) print(last[v], S2);
        	if(DP(v, step+1, S2)) Out(v, step+1, S2, s + char('a'+i));
        }
    }


}ac;



int main() {
   int kase = 0;
   while(scanf("%d%d", &n, &m) && n) {
      ac.init();
      memset(dp, -1, sizeof dp);
      for(int i = 1; i <= m; i++) {
          scanf("%s", s);
          if(!ac.insert(s, i)) { m--; i--; }
      }
      ac.getFail();
      LL ans = ac.DP(0, 0, 0);
      printf("Case %d: %lld suspectsn", ++kase, ans);
      if(ans <= 42) { ac.Out(0, 0, 0, ""); }
   }
   return 0;
}