【loj10061】最短母串
2024-09-08 06:13:38
题目描述
原题来自:HNOI 2006
给定 n个字符串 S1,S2,⋯,Sn 要求找到一个最短的字符串 T,使得这 n 个字符串都是 T 的子串。
输入格式
第一行是一个正整数 n,表示给定的字符串的个数;
以下的 n 行,每行有一个全由大写字母组成的字符串。
输出格式
只有一行,为找到的最短的字符串 T。
在保证最短的前提下,如果有多个字符串都满足要求,那么必须输出按字典序排列的第一个。
样例
样例输入
2
ABCD
BCDABC
样例输出
ABCDABC
数据范围与提示
对于全部数据,1≤n≤12,1≤∣Si∣≤50。
题意:(挂loj是因为我的解法在bzoj上T了并且我不想调QAQ)
给你$n$个字符串,求他们的最短母串,即求一个最短字符串使得这$n$个字符串都是它的子串。若长度相同输出字典序最小的。
题解:
建出$AC$自动机后问题转化成找一条最短的路径覆盖所有$end$节点。
那么我们可以考虑对每个节点维护一个压缩状态表示从根走到该点包含了哪些字符串。
然后从根开始沿$bfs$序遍历(保证字典序最小)并记录路径,若合法则输出答案。
这题主要是教会了我一个真理:
当你发现某个代码已经改不出来的时候,重构代码总是会给你惊喜……
代码:
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue> using namespace std;
#define MAXN 15
#define MAXM 605
#define ll long long struct node{
int son[],s;
}tree[MAXM];
struct way{
int las; char ch;
}p[MAXM*(<<MAXN)];
int tot=,nxt[MAXM];
bool vis[MAXM][<<MAXN];
char str[MAXN],ans[MAXN];
inline int read(){
int x=,f=;
char c=getchar();
for(;!isdigit(c);c=getchar())
if(c=='-')
f=-;
for(;isdigit(c);c=getchar())
x=x*+c-'';
return x*f;
} inline void add(int p,char *str){
int N=strlen(str),u=;
for(int i=;i<N;i++){
int ch=str[i]-'A';
if(!tree[u].son[ch])
tree[u].son[ch]=++tot;
u=tree[u].son[ch];
}
tree[u].s|=(<<p);
return;
} inline void get_nxt(){
for(int i=;i<;i++)
tree[].son[i]=;
queue<int> q; q.push();
while(!q.empty()){
int u=q.front(); q.pop();
for(int i=;i<;i++){
if(tree[u].son[i]){
q.push(tree[u].son[i]);
nxt[tree[u].son[i]]=tree[nxt[u]].son[i];
tree[tree[u].son[i]].s|=tree[tree[nxt[u]].son[i]].s;
}
else tree[u].son[i]=tree[nxt[u]].son[i];
}
}
return;
} inline void solve(int N){
int end=(<<N)-;
queue<int> q1,q2;
q1.push(); q2.push();
int hd=,tl=;
while(!q1.empty() && !q2.empty()){
int u=q1.front();q1.pop();
int sta=q2.front();q2.pop();
if(sta==end){
int cnt=;
for(;hd>;hd=p[hd].las)
ans[++cnt]=p[hd].ch;
for(int i=cnt;i>=;i--)
printf("%c",ans[i]);
printf("\n");
return;
}
for(int i=;i<;i++){
if(!vis[tree[u].son[i]][(tree[tree[u].son[i]].s)|(sta)]){
vis[tree[u].son[i]][(tree[tree[u].son[i]].s)|(sta)]=;
q1.push(tree[u].son[i]);
q2.push((tree[tree[u].son[i]].s)|(sta));
p[++tl].las=hd,p[tl].ch=i+'A';
}
}
hd++;
}
return;
} int main(){
int N=read();
for(int i=;i<N;i++)
scanf("%s",str),add(i,str);
get_nxt(); solve(N);
return ;
}
最新文章
- Unity引擎IOS执行档大小优化
- 淘宝美工一站式:淘宝ps高级美工技巧视频教程,HTML代码学习【教程下载
- 从头开始写框架(一):浅谈JS模块化发展
- CEF 相关资料
- 第2章 面向对象的设计原则(SOLID):2_里氏替换原则(LSP)
- BZOJ1172 : [Balkan2007]Dream
- nginx模块编程之获取客户ip及端口号
- Java NIO与IO的差别和比較
- 使用val()方法设置表单中的默认选中项
- 使用PDO执行SQL语句exec()、query()
- memcache学习使用
- [ASP.NET]利用itextsharp将GridView汇出PDF档
- HTTPClient和URLConnection核心区别分析
- Orchard
- 前端基础之初识 HTML
- [Python Study Notes]计算cpu使用率
- javascript常见问题总结
- [matlab] 6.粒子群优化算法
- 【Json】1、JSON 数据格式
- python新建txt文件,并逐行写入数据
热门文章
- org.hibernate.id.IdentifierGenerationException错误解决方法
- vc6.0的一些快捷键
- POJ 2586 Y2K Accounting Bug(枚举大水题)
- java学习方向及主要内容
- 按行读入xml文件,删除不需要的行 -Java
- Ubuntu 配置 nfsserver
- KMP 、扩展KMP、Manacher算法 总结
- Hadoop的jobhistoryserver配置
- How to run Media SDK samples on Skylake【转载】
- hadoop datanode启动失败(All directories in dfs.data.dir are invalid)