最短字符串
有 (n) 个由 ( exttt{A,G,C,T}) 组成的小字符串，构造一个大字符串 (S) ，使得每个小字符串是 (S) 的子串，最短的串 (S) 需要多长？
多组数据。
(Tleq20,nleq10, ext{字符串长度}leq20)
题解
想到了用状压记录某个字符串出没出现过，但是后面用着错误的状压 dp ……
正解：建立出 trie图 后，在trie 图上进行 bfs ，同时用状压记录某个字符串是否出现。一旦全部出现立即输出。
#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int INF = 0x3f3f3f3f,N = 12,M = 22;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
ll ret=0;char ch=' ',c=getchar();
while(!(c>='0'&&c<='9'))ch=c,c=getchar();
while(c>='0'&&c<='9')ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
int n,k;
template <typename T> struct que{
T a[N*M]; int st=1,ed=0;
que(){st=1,ed=0;}
inline void clear(){st=1,ed=0;}
inline int size(){return ed-st+1;}
inline bool empty(){return !(ed-st+1);}
inline T front(){return a[st];}
inline T back(){return a[ed];}
inline void pop_front(){st++;}
inline void pop_back(){ed--;}
inline void push(T x){a[++ed] = x;}
inline T operator [] (int x){return a[st+x-1];}
};
inline int getch(char ch){return ch == 'A' ? 1 : ch == 'G' ? 2 : ch == 'C' ? 3 : 4;}
int dp[(1<<10)+5][N*M];
struct ACauto{
int c[N*M][5],fail[N*M],tot = 1;
int sta[N*M];
bool vis[N*M][(1<<10)+5];
struct node{int p,s,w;};
void init(){
memset(c,0,sizeof(c));
memset(fail,0,sizeof(fail));
memset(sta,0,sizeof(sta));
memset(vis,0,sizeof(vis));
tot = 1;
}
void insert(char ch[],int id){
int p = 1 , len = strlen(ch+1);
for(int i = 1 ; i <= len ; i ++){
int v = getch(ch[i]);
if(!c[p][v]) c[p][v] = ++tot;
p = c[p][v];
}
sta[p] |= 1<<(id-1);
}
void build(){
for(int i = 1 ; i <= 4 ; i ++) c[0][i] = 1;
que <int> q; q.push(1);
while(!q.empty()){
int p = q.front(); q.pop_front();
sta[p] |= sta[fail[p]];
for(int i = 1 ; i <= 4 ; i ++)
if(c[p][i]) fail[c[p][i]] = c[fail[p]][i], q.push(c[p][i]);//, printf(" fail[%d] = %d
",c[p][i],fail[c[p][i]]);
else c[p][i] = c[fail[p]][i];
}
}
void bfs(){
queue <node> q;
while(!q.empty()) q.pop();
q.push((node){1,0,0});
vis[1][0] = 1;
while(!q.empty()){
node u = q.front(); q.pop();
// printf(" (%d,%d)
",u.p,u.s);
if(u.s == (1<<n)-1){printf("%d
",u.w); return;}
for(int i = 1 ; i <= 4 ; i ++){
int p = c[u.p][i], s = u.s | sta[p];
if(vis[p][s]) continue;
vis[p][s] = 1;
q.push((node){p,s,u.w+1});
}
}
}
}ac;
char ch[M];
void work(){
ac.init();
n = read();
for(int i = 1 ; i <= n ; i ++)
scanf("%s",ch+1),
ac.insert(ch,i);
ac.build();
ac.bfs();
}
signed main(){
int T = read();
while(T--) work();
return 0;
}