题目描述

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

输入

第一行是一个正整数n（n<=12），表示给定的字符串的个数。

以下的n行，每行有一个全由大写字母组成的字符串。每个字符串的长度不超过50.

输出

只有一行，为找到的最短的字符串T。在保证最短的前提下，

如果有多个字符串都满足要求，那么必须输出按字典序排列的第一个。

样例输入

2

ABCD

BCDABC

样例输出

ABCDABC

 

题意是找一个最短的母串包含所有给出的字符串，多模匹配显然是AC自动机，把给出的所有串建在AC自动机上，问题就可以转化成了在AC自动机上经过所有串的终止节点所走的最少步数是多少。因为给出的串很少，所以可以用二进制来表示已经经过了哪个串的终止节点。然后用bfs(保证母串最短)按字典序(保证答案是字典序排列第一个)跑最短路并记录中间路径直到走到某个点的状态是(1<<n)-1为止。可以把整个过程看成是分层图(一个状态是一层)最短路，每个点在每个状态下只能遍历一次，当到达（1<<n）-1那一层就代表找到了最短母串。

最后附上代码。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int n;int cnt;int num;char s[100];int t1[2460000];int t2[2460000];int end[605];int ans[605];int fail[1000];int a[605][26];int vis[605][4100];void build(char *s,int x){ int now=0; int len=strlen(s); for(int i=0;i
            

q; for(int i=0;i<26;i++) { if(a[0][i]) { fail[a[0][i]]=0; q.push(a[0][i]); } } while(!q.empty()) { int now=q.front(); q.pop(); for(int i=0;i<26;i++) { if(a[now][i]) { fail[a[now][i]]=a[fail[now]][i]; end[a[now][i]]|=end[a[fail[now]][i]]; q.push(a[now][i]); } else { a[now][i]=a[fail[now]][i]; } } } return ;}void bfs(){ queue

q1; queue

q2; q1.push(0); q2.push(0); int l=1; int r=1; while(l<=r) { int now=q1.front(); int e=q2.front(); q1.pop(); q2.pop(); if(e==((1<

1;l=t2[l]) { ans[++num]=t1[l]; } for(int i=num;i;i--) { printf("%c",ans[i]+'A'); } return; } for(int i=0;i<26;i++) { if(!vis[a[now][i]][e|end[a[now][i]]]) { t1[++r]=i; t2[r]=l; q1.push(a[now][i]); q2.push(e|end[a[now][i]]); vis[a[now][i]][e|end[a[now][i]]]=1; } } l++; }}int main(){ scanf("%d",&n); for(int i=0;i