/*

难的不是ac自动机,是状态压缩dp

之前做了一两题类似题目,感觉理解的还不够透彻

*/

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int mxn=;
int L1[mxn*(<<)],L2[mxn*(<<)];
queue<int>q1,q2;
bool vis[mxn][(<<)];
int n;
int ans[mxn],num=;
struct ACa{
int t[mxn][];
int fail[mxn];
int end[mxn];
int S,cnt;
int q[],hd,tl;
void init(){S=cnt=;memset(end,,sizeof end);return;}
void insert(char *s,int id){
int len=strlen(s),now=S;
for(int i=;i<len;i++){
if(!t[now][s[i]-'A'])t[now][s[i]-'A']=++cnt;
now=t[now][s[i]-'A'];
}
end[now]|=(<<id);
}
void Build(){
hd=;tl=;
for(int i=;i<;i++)
if(t[S][i]){q[++tl]=t[S][i];fail[t[S][i]]=S;}
else t[S][i]=S;
while(hd<=tl){
int u=q[hd++];
int v,r;
for(int i=;i<;i++){
if(t[u][i]){
fail[t[u][i]]=t[fail[u]][i];
end[t[u][i]]|=end[t[fail[u]][i]];
q[++tl]=t[u][i];
}
else t[u][i]=t[fail[u]][i];
}
}
return;
}
void solve(){
hd=;tl=;int ed=(<<n)-;
q1.push(S),q2.push();
while(hd<=tl){
int u=q1.front();q1.pop();
int e=q2.front();q2.pop();
// printf(" e:%d\n",e);
if(e==ed){//结束状态
for(;hd>;hd=L2[hd]){ans[++num]=L1[hd];}
for(int i=num;i;i--)printf("%c",ans[i]+'A');
return;
}
for(int i=;i<;i++){
if(!vis[t[u][i]][e|end[t[u][i]]]){
L1[++tl]=i;
L2[tl]=hd;
q1.push(t[u][i]);
q2.push(e|end[t[u][i]]);
vis[t[u][i]][e|end[t[u][i]]]=;
}
}
hd++;
}
}
}ac;
char s[];
int main(){
int i,j;
scanf("%d",&n);
ac.init();
for(i=;i<n;i++)scanf("%s",s),ac.insert(s,i);
// for(i=1;i<=ac.cnt;i++)if(ac.end[i])printf("%d %d\n",i,ac.end[i]);
ac.Build();
ac.solve();
return ;
}

最新文章

  1. Excel 行列转置 解决竖向拉,字母跟着递增的问题
  2. JustSniffer
  3. 将 Android 应用移植到 BlackBerry PlayBook 上
  4. 安装TokuDB引擎
  5. iOS程序性能优化
  6. Android实现资料收藏
  7. Delphi - 闲来无事,自己写个Timer玩玩(多线程Timer)
  8. Java IO流之普通文件流和随机读写流区别
  9. ADO.NET中的五大对象
  10. [JZOJ5511] 送你一个DAG
  11. LeetCode 2
  12. SAP 跨公司销售业务
  13. SQL数据库日志清理
  14. Java调用第三方接口示范
  15. doctrine/annotation 的简单使用
  16. 【Linux】linux/unix下telnet提示Escape character is &#39;^]&#39;的意义
  17. log4js 2.X版本配置详解
  18. [记录] CSS 左边元素定长,右边元素获得剩余长度
  19. C# Excel转换为Json
  20. Expo大作战(二十六)--expo sdk api之Video和WebBrowser

热门文章

  1. renren-security旧版本 分模块 的模块之间关系浅析
  2. IntelliJ IDEA执行maven 跳过test
  3. 省电优化之WakeLock
  4. Javascript - ExtJs - 组件 - 分页
  5. SpringSecurity实现记住我功能
  6. 【转】HTML
  7. ROC和AUC理解
  8. python序列化模块的速度比较
  9. linux下添加删除,修改,查看用户和用户组
  10. 其他-n个互相独立的连续随机变量中第i小的数值期望