[BZOJ1559]密码

数据范围特别小，考虑状压DP

因为要求给定的字符串在母串中出现，所以可以用AC自动机辅助DP

因为AC自动机不能处理模式串互相包含的情况，所以先把互相包含的串去掉（暴力就行，数据范围太小）

因为要状压DP，所以建trie时要存$num_x$表示节点$x$表示的串的编号

$f_{i,j,k}$表示已经匹配了母串的前$i$位，现在在AC自动机的节点$j$上，匹配模式串状态为$k$的方案数，如果trie中有$j\mathop\rightarrow\limits^cl$，那么用$f_{i,j,k}$更新$f_{i+1,l,k\cup num_l}$即可，第一维可以滚动

因为这题中只要求“出现”，所以建trie时如果不存在$x\mathop\rightarrow\limits^c$，那么直接把这条边连向$fail_x\mathop\rightarrow\limits^c$指向的节点即可（不需要管出现位置，出现就行）

答案$\leq42$时要求输出方案，注意到这时母串一定不存在位置不与模式串匹配（否则答案最小的情况是母串匹配一个模式串，还有一位可以随意选字符，有$2\times26=52\gt42$种方案）

直接暴搜即可，为方便处理可以预处理$link_{i,j}$表示第$i$个模式串的后缀与第$j$个模式串的前缀的最长匹配长度（同样是暴力处理...）

DP值会爆long long

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int ch[110][26],fail[110],num[110],q[110],M,cnt;
void insert(char*s,int p){
	int i,x,f;
	x=0;
	for(i=0;s[i];i++){
		f=s[i]-'a';
		if(ch[x][f]==0)ch[x][f]=++M;
		x=ch[x][f];
	}
	num[x]=1<<(p-1);
}
void getfail(){
	int head,tail,x,y,i;
	head=1;
	tail=0;
	for(i=0;i<26;i++){
		y=ch[0][i];
		if(y){
			tail++;
			q[tail]=y;
		}
	}
	while(head<=tail){
		x=q[head];
		head++;
		for(i=0;i<26;i++){
			y=ch[x][i];
			if(y){
				fail[y]=ch[fail[x]][i];
				tail++;
				q[tail]=y;
			}else
				ch[x][i]=ch[fail[x]][i];
		}
	}
}
char s[20][20];
int len[20],link[20][20];
int getlink(int x,int y){
	int i,j;
	bool flag;
	for(i=min(len[x],len[y]);i>0;i--){
		flag=1;
		for(j=0;j<i;j++){
			if(s[x][len[x]-i+j]!=s[y][j]){
				flag=0;
				break;
			}
		}
		if(flag)break;
	}
	return i;
}
bool del[20],v[20];
char ans[50][30];
int pos[20],L,n,tot;
void dfs(int x){
	int i,j,k;
	if(x>cnt){
		tot++;
		k=0;
		for(i=1;i<x;i++){
			for(j=link[pos[i-1]][pos[i]];j<len[pos[i]];j++){
				ans[tot][k]=s[pos[i]][j];
				k++;
			}
		}
		if(k!=L)tot--;
		return;
	}
	for(i=1;i<=n;i++){
		if(!del[i]&&!v[i]){
			v[i]=1;
			pos[x]=i;
			dfs(x+1);
			v[i]=0;
		}
	}
}
bool cmp(int x,int y){
	for(int i=0;i<L;i++){
		if(ans[x][i]!=ans[y][i])return ans[x][i]<ans[y][i];
	}
	return 0;
}
ll f[2][110][1024];
int rk[50];
int main(){
	int i,j,k,l,t,x;
	ll ans;
	scanf("%d%d",&L,&n);
	for(i=1;i<=n;i++){
		scanf("%s",s[i]);
		len[i]=strlen(s[i]);
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++)link[i][j]=getlink(i,j);
	}
	cnt=n;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(i!=j&&!del[i]&&!del[j]&&len[i]>=len[j]&&strstr(s[i],s[j])!=0){
				del[j]=1;
				cnt--;
			}
		}
	}
	for(i=1;i<=n;i++){
		if(!del[i])insert(s[i],i);
	}
	getfail();
	t=0;
	f[0][0][0]=1;
	for(i=0;i<L;i++){
		memset(f[t^1],0,sizeof(f[t^1]));
		for(j=0;j<=M;j++){
			for(k=0;k<1<<n;k++){
				if(f[t][j][k]){
					for(l=0;l<26;l++){
						x=ch[j][l];
						f[t^1][x][k|num[x]]+=f[t][j][k];
					}
				}
			}
		}
		t^=1;
	}
	x=0;
	for(i=1;i<=n;i++){
		if(!del[i])x|=1<<(i-1);
	}
	ans=0;
	for(i=0;i<=M;i++)ans+=f[t][i][x];
	printf("%lld\n",ans);
	if(ans<=42){
		dfs(1);
		for(i=1;i<=tot;i++)rk[i]=i;
		sort(rk+1,rk+tot+1,cmp);
		for(i=1;i<=tot;i++){
			for(j=0;j<L;j++)putchar(::ans[rk[i]][j]);
			putchar('\n');
		}
	}
}

巴特西

[BZOJ1559]密码

最新文章

热门文章