题解——P4045 [JSOI2009]密码
题目传送门
题意
给定 \(n\) 个模式串，求长度为 \(L\) 且包含所有模式串的文本串个数，若个数小于等于 \(42\)，则按字典序升序输出全部文本串。
思路+实现
（1）AC自动机
首先多模式串匹配问题自然会想到AC自动机。
其次，当一个状态 \(u\) 的
失配指针 \(f\) 包含某个模式串，那么 \(u\) 也包含该模式串，于是在构建失配指针时，可以预处理出每个节点所包含的模式串状态。
struct AC_Automaton{
int tr[105][26],tot,fail[105],mark[105];
inline void insert(int k){
int u=0,l=strlen(s[k]+1);
for(int i=1;i<=l;++i){
if(!tr[u][s[k][i]-'a']) tr[u][s[k][i]-'a']=++tot;
u=tr[u][s[k][i]-'a'];
}
mark[u]|=(1<<(k-1));
}
inline void build(){
queue q;
for(int i=0;i<26;i++){
if(tr[0][i]) q.push(tr[0][i]);
}
while(!q.empty()){
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]);
mark[tr[u][i]]|=mark[tr[fail[u]][i]];
}
else tr[u][i]=tr[fail[u]][i];
}
}
}
}ac;
（2）状压dp
与P4052 文本生成器的思路相似，我们考虑dp。
简单概述一下文本生成器那题的思路，因为“至少包含一个模式串”与“不包含任何模式串”是“互补”关系，所以我们求不包含任何模式串的方案数即可；不过本题要求包含所有模式串的方案数，需要在转移中附带当前状态（如果是不包含直接只选择没有标记的节点即可）。
设置 \(dp(i,j,u)\)，标记长度为 \(i\)，当前已经包含的模式串状态为 \(j\)，当前节点是 \(u\) 的方案数。我们令 \(u\) 向下的一个节点为 \(v\)，用刷表法，可以得到：\(dp(i+1,j|mark(v),v)=\sum dp(i,j,u)\)，最后统计 \(\sum_{i=0}^{tot} dp(L,(1<
dp[0][0][0]=1;
for(int i=0;i<=len;i++){
for(int j=0;j<(1<
（3）输出方案
因为当答案小于等于 \(42\) 时才输出方案，且转移过程中不便记录方案，我们可以考虑最后 \(dfs\) 输出方案。
观察 \(42\) 这个数，貌似没有特别之处，但恰恰因为它很小，所以所有文本串都不会存在空余位置，比如模式串为 \(\text{down}\) 和 \(\text{need}\)，要求长度为 \(8\)，因为存在重叠的首尾，所以某些文本串可以写作形如 \(\text{needownX}\) 的样子，而同时这个 \(\text{X}\) 也可以放在文本串首，那么此时就已经有 \(52\) 种选择了，是一定不在输出方案的范围内的。
换言之，文本串一定是“紧凑”的，所以我们只需要预处理出任意两个模式串的首尾重复长度，\(dfs\) 判断长度是否等于 \(L\) 并按字典序输出即可。
inline void dfs(int x){
if(x==n+1){
string now="";
for(int i=1;i<=n;i++){
//l[i][j]表示第i个模式串的后缀与第j个模式串前缀的重合长度
int pos=(i==1)?0:l[ord[i-1]][ord[i]];
for(int j=pos+1;j<=strlen(s[ord[i]]+1);j++){
now+=s[ord[i]][j];
}
}
if(now.size()==len){
_out.push_back(now);
}
return;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=1,ord[x]=i;
dfs(x+1);
vis[i]=0,ord[x]=0;
}
}
}
相关