AC自动机专题:配合状压dp-HDU2825

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2825

题目大意:

一个长度为n($n\le 10$)的序列。每个取值为 ‘a’ 到 ‘z’. 然后给你m($m\le 10$)个长度小于10的字符串。问你至少含有k个不同字符串(不同字符串可能互相重叠覆盖)的序列的方案数.

题目思路:

不难想出状态:$dp(i,j,states)$代表序列的前i位且在Trie图上的j节点并且生成的序列中字符串含有的状态为$states$的方案数。在利用刷表法(我为人人)即可.

题目中提醒了,当字符串同时含有she 和 he 这种重叠字符串时，是要算两个的。所以这里在建AC自动机的时候要注意将危险标记传递下去。利用fail指针即可。(节点X的fail指针的含义就是以X为节点的前缀字符串的后缀集合链)

AC代码:

#include<bits/stdc++.h> using namespace std; const int maxn = 100 + 5; const int mod = 20090717; int n; int dp[30][105][1<<10]; namespace AC{ int tr[maxn][26] , tot; int fail[maxn] , S[maxn]; void init (){ tot = 0; for (int i = 0 ; i < maxn ; i++) { for (int j = 0 ; j < 26 ; j++){ tr[i][j] = 0; } fail[i] = S[i] = 0; } } void add (char * s , int g){ int u = 0; for (int i = 1 ; s[i] ; i++){ if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot; u = tr[u][s[i] - 'a']; } S[u] = (1 << (g - 1)); } queue<int>q; void build (){ while (q.size()) q.pop(); 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]; } } // 这里注意要传递危险节点状态 S[u] |= S[fail[u]]; } } } char s[maxn]; char tmp[250]; int cnt[1 << 10]; int main() { int n , m , t; cnt[0] = 0; for (int i = 1 ; i < (1 << 10) ; i++) cnt[i] = cnt[i >> 1] + (i & 1); while (scanf("%d%d%d" , &n , &m , &t) , n){ AC::init(); for (int i = 0 ; i <= n ; i++){ for (int j = 0 ; j <= 100 ; j++){ for (int k = 0 ; k < (1 << m) ; k++){ dp[i][j][k] = 0; } } } for (int i = 1 ; i <= m ; i++){ scanf("%s" , tmp + 1); AC::add(tmp , i); } AC::build(); dp[0][0][0] = 1; for (int i = 0 ; i < n ; i++){ for (int j = 0 ; j <= AC::tot ; j++){ for (int k = 0 ; k < (1 << m) ; k++){ if (!dp[i][j][k]) continue; for (int g = 0 ; g < 26 ; g++){ dp[i + 1][AC::tr[j][g]][ k | AC::S[AC::tr[j][g]] ] = (dp[i + 1][AC::tr[j][g]][ k | AC::S[AC::tr[j][g]] ] + dp[i][j][k]) % mod; } } } } int ans = 0; for (int i = 0 ; i <= AC::tot ; i++){ for (int k = 0 ; k < (1 << m) ; k ++){ if (cnt[k] < t) continue; // cout << i << " " << k << " " << dp[n][i][k] << endl; ans = (ans + dp[n][i][k]) % mod; } } printf("%d\n" , ans); } return 0; }