[BZOJ1559]-[JSOI2009]密码-补全AC自动机+状压dp

说在前面

这个题的代码真的恶心…AC自动机上dp就算了，居然还要输出方案= =???（黑人问号脸.jpg）
本来计划着今天把AC自动机（补全）和trie搞了。在一个讲稿里发现了这个题，看的顺眼决定去写一写=w=
然后被这道题折磨致死…吃饭之前就开始写，一直写到21:09才AC

题目

BZOJ1559传送门
原题是图片，就不粘题面了…
这题没有权限，可以进去看

解法

（因为是在一个讲稿里发现的所以…已经知道了大概是AC自动机+dp。）
直接讲做法吧…建出AC自动机，补全，然后跑状压DP。
以下给定串代表输入的串，字母串代表符合题意的答案串。

因为题目是要统计合法的字母串数，而这个答案可能很大。所以要么是数论（或者乘法原理相关）要么是DP
然而稍微一想，就可以把第一个作法给cut掉，因为字符串之间可能相交，排列顺序也很多，并且字符串与字符串之间还可以随意添加字母，用数学方法几乎是不可解的。所以基本咬定DP
给定串总共只有10个，而最后只有全部包含这些给定串的字母串才合法，不难想到可以把「给定串是否在字母串中出现过」压位，也就是状压。看一看数据范围也能确定这个想法（至少有可过的可能性）

不难想到dp数组。定义dp数组dp[i][state][j]表示当前已经选了第i个字母，包含状态为state，在第j个节点上（注意是节点而不是字母，不然无法转移，可以自己想一想）。每个位置都有26种选择，如果当前节点有这个儿子，就直接转移到儿子，如果没有，就需要跳fail进行转移。在实现的时候，为了避免重复跳fail（转移代价太大），选择补全AC自动机。

另外关于为什么dp数组第三维要定义成节点而不是字母，因为在trie上，一个节点代表的是一个字符串的前缀。如果在下一步选了一个当前节点有的儿子，就直接进去。如果选择的是当前没有的儿子，就去找失配，前面已经匹配上的但是在失配之后消失掉的那一截字符串，就相当于是选择了给定串之外的随意字符。所以某个节点和他的fail虽然字母是一样的，但是含义不一样，因此这样定义是不会重复计算的。

关于输出方案，直接根据dp数组倒推回去即可，枚举所有节点，对于可以转移到当前状态的节点就递归下去，细节看代码。

下面是自带大常数的代码

#include 
#include 
#include 
#include 
using namespace std ;bool ignore[15] ;
char ss[15][15] ;
int L , N ;
long long dp[27][1<<11][110] , ans ;
struct Node{int id , isend ;char now ;Node* ch[26] , *fail ;
}w[2005] , *tw = w , *root ;bool inside( int x , int y ){int lenx = strlen( ss[x] ) , leny = strlen( ss[y] ) ;if( lenx < leny ) return false ;for( int i = 0 , j , tmp ; i < lenx ; i ++ ){for( j = 0 , tmp = i ; j < leny && tmp < lenx ; j ++ ,tmp ++ )if( ss[x][tmp] != ss[y][j] ) break ;if( j == leny ) return true ;}return false ;
}void preWork(){for( int i = 1 ; i <= N ; i ++ )for( int j = 1 ; j <= N ; j ++ ){if( i == j ) continue ;if( strcmp( ss[i] , ss[j] ) == 0 ) ignore[ max(i,j) ] = true ;else if( inside( i , j ) ) ignore[j] = true ;}int tmp = 0 ;for( int i = 1 ; i <= N ; i ++ ){if( ignore[i] ) continue ;++ tmp ;for( int j = 0 ; j <= 10 ; j ++ )ss[tmp][j] = ss[i][j] ;}N = tmp ;
}void Insert( Node *nd , char *cc , int Emm ){int len = strlen( cc ) ;for( int i = 0 ; i < len ; i ++ ){//  printf( "i(%d) nd_ads(%d) char(%c)\n" , i , nd , nd->now ) ;int id = cc[i] - 'a' ;if( !nd->ch[id] ){nd->ch[id] = ++tw ;nd->ch[id]->now = cc[i] ;nd->ch[id]->id = tw - w ;}nd = nd->ch[id] ;}nd->isend = Emm ;
}queue que ;
void getFail(){que.push( root ) ;while( !que.empty() ){Node *u = que.front() ; que.pop() ;for( int i = 0 ; i < 26 ; i ++ ){Node *&v = u->ch[i] ;Node *p = u->fail ;while( p && !p->ch[i] ) p = p->fail ;if( v ){v->fail = ( p ? p->ch[i] : root ) ;que.push( v ) ;} else v = ( p ? p->ch[i] : root ) ;}}
}char anstr[45][45] ;
int sta[45] , topp , cntstr , rank[45] ;
void dfs( int left , int state , int nowid , int c ){if( left == 0 ){//if( state ) return ;cntstr ++ ;for( int i = 0 ; i < L ; i ++ )anstr[cntstr][i] = sta[i] ;anstr[cntstr][L] = 0 ;return ;}sta[left-1] = c + 'a' ;for( int i = 1 ; i <= tw - w ; i ++ ){if( dp[left-1][state][i] && w[i].ch[c]->id == nowid )dfs( left - 1 , state , w[i].id , w[i].now - 'a' ) ;}if( w[nowid].isend ){int x = ( 1 << ( w[nowid].isend - 1 ) ) ;if( (state&x) == 0 ) return ;for( int i = 1 ; i <= tw - w ; i ++ ){if( dp[left-1][state^x][i] && w[i].ch[c]->id == nowid )dfs( left - 1 , state^x , w[i].id , w[i].now - 'a' ) ;}}
}bool cmp( const int &i , const int &j ){for( int k = 0 ; k < L ; k ++ )if( anstr[i][k] != anstr[j][k] )return anstr[i][k] < anstr[j][k] ;return false ;
}void solve(){root = ++tw ; root->id = 1 ;for( int i = 1 ; i <= N ; i ++ )Insert( root , ss[i] , i ) ;getFail() ;int Fstate = ( 1 << N ) - 1 , totnd = tw - w ;dp[0][0][1] = 1 ;for( int i = 0 ; i <= L ; i ++ ){for( int S = 0 ; S <= Fstate ; S ++ ){for( int k = 1 ; k <= totnd ; k ++ ){if( !dp[i][S][k] ) continue ;for( int f = 0 , news , id ; f < 26 ; f ++ ){if( w[k].ch[f]->isend )news = ( 1 << ( w[k].ch[f]->isend - 1 ) ) ;else news = 0 ;id = w[k].ch[f]->id ;dp[i+1][S|news][id] += dp[i][S][k] ;}}}}for( int i = 1 ; i <= totnd ; i ++ )ans += dp[L][Fstate][i] ;printf( "%lld\n" , ans ) ;if( ans <= 42 ){for( int i = 1 ; i <= totnd ; i ++ ){if( dp[L][Fstate][i] )dfs( L , Fstate , i , w[i].now - 'a' ) ;}for( int i = 1 ; i <= ans ; i ++ )rank[i] = i ;sort( rank + 1 , rank + ans + 1 , cmp ) ;for( int i = 1 ; i <= ans ; i ++ )printf( "%s\n" , anstr[ rank[i] ] ) ;}
}int main(){scanf( "%d%d" , &L , &N ) ;for( int i = 1 ; i <= N ; i ++ )scanf( "%s" , ss[i] ) ;preWork() ;solve() ;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！