bzoj1195 [HNOI2006]最短母串

bzoj1195 [HNOI2006]最短母串

​​ Description 给定n个字符串（S1,S2,„,Sn），要求找到一个最短的字符串T，使得这n个字符串（S1,S2,„,Sn）都是T的子串。

Input 第一行是一个正整数n（n<=12），表示给定的字符串的个数。 以下的n行，每行有一个全由大写字母组成的字符串。每个字符串的长度不超过50. Output 只有一行，为找到的最短的字符串T。在保证最短的前提下， 如果有多个字符串都满足要求，那么必须输出按字典序排列的第一个。 Sample Input 2 ABCD BCDABC Sample Output ABCDABC HINT

Source AC自动机忘了调试很久 卡内存 调试很久？

设dp[i][s]表示现在在AC自动机上的第i个节点我现在匹配了s状态的串最短需要几个字母完全匹配 因为要求字典序最小 所以我直接贪心的从0~25转移并且 采用bfs的方法 即使得最后匹配出来的是最短的 往子树走 因为子树可能包含更多的串

#include#include#include#include#define fi first#define se second#define pa pair#define mp(x,y) make_pair(x,y)#define Pa pair >using namespace std;const int N=602;char s[66];int trans[N][26],q1[N],top,n,end[N],fail[N],cnt=1;inline void insert1(int id){ scanf("%s",s+1);int p=1; for (int i=1,nxt;s[i];++i){ if (!trans[p][s[i]-'A']) trans[p][s[i]-'A']=nxt=++cnt; else nxt=trans[p][s[i]-'A'];p=nxt; }end[p]|=1<q;q.push(1);for (int i=0;i<26;++i) trans[0][i]=1; while(!q.empty()){ int x=q.front();q.pop(); for (int i=0;i<26;++i){ int &y=trans[x][i]; if (!y) {y=trans[fail[x]][i];continue;} fail[y]=trans[fail[x]][i];q.push(y);end[y]|=end[fail[y]]; } }}pa pre[N][4100];bool visit[N][4100];int pre1[N][4100];int main(){ freopen("bzoj1195.in","r",stdin); scanf("%d",&n);int S=(1< q;q.push(mp(1,0));int h=1,t=1; while(!q.empty()){ pa t=q.front();q.pop(); int x=t.fi,s=t.se; if (s==S){ pa tmp=mp(x,s); while(1){ q1[++top]=pre1[tmp.fi][tmp.se]; int x=tmp.fi,s=tmp.se; tmp=pre[x][s]; if (tmp.fi==1&&tmp.se==0) break; } for (int i=top;i;--i)putchar(q1[i]+'A'); return 0; } for (int i=0;i<26;++i){ int y=trans[x][i]; if (visit[y][s|end[y]]) continue; q.push(mp(y,s|end[y])); pre[y][s|end[y]]=mp(x,s); pre1[y][s|end[y]]=i; visit[y][s|end[y]]=1; } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。