最短母串问题

link

考虑建立AC自动机，然后在自动机上跑广搜。扩展的时候默认A到Z就可以保证字典序最小，而AC自动机的特性又可以帮助完成拼接的任务。数据似乎比较水，听说爆搜可以过，但我没写过。

#include
using namespace std;
//#define zczc
const int N=1010;
const int S=12;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}

int m,cnt;
char w[N];
struct node{
	int fail,num,next[26];
}a[N];
inline void insert(int wh){
	scanf("%s",w);int len=strlen(w);
	for(int i=0,x=0;iq;
void pre(){
	for(int i=0;i<26;i++){
		if(a[0].next[i])q.push(a[0].next[i]);
	}
	while(!q.empty()){
		int now=q.front();q.pop();
		for(int i=0;i<26;i++){
			int ff=a[now].fail;
			if(a[now].next[i]){
				a[a[now].next[i]].fail=a[ff].next[i];
				q.push(a[now].next[i]);
			}
			else a[now].next[i]=a[ff].next[i];
		}
	}
}

struct nd{
	int val,wh;string st;
};
queueqq;
bool vis[N][(1<