题目链接：
http://codeforces.com/gym/101194
题意：
给n个字符串s1,s2......sn，问只在第一个字符串中出现的最短子串，多个答案输出字典序最小的子串。
思路：
把n个串用'z'+1连接起来建立后缀自动机，把s2到sn的母串上所有位置都标记cnt=1，如果parent树的子树和求完后，某个状态的cnt==0，那么所有能到达该状态的串都只在s1中出现过，于是求从root到这些cnt==0的状态的字典序最小的最短路就好了。
Time：420ms
#include<bits/stdc++.h>
using namespace std;
const int N=600005;
int tot,root,last;
int pa[N],deep[N],ch[N][27],cnt[N];
int newnode(int _deep)
{
tot++;
memset(ch[tot],0,sizeof(ch[tot]));
deep[tot]=_deep;
cnt[tot]=0;
return tot;
}
void init()
{
tot=0;
root=newnode(0);
last=root;
}
void insert(int w)
{
int np=newnode(deep[last]+1);
int u=last;
while(u&&!ch[u][w]) ch[u][w]=np,u=pa[u];
if (!u) pa[np]=root;
else
{
int v=ch[u][w];
if (deep[u]+1==deep[v]) pa[np]=v;
else
{
int nv=newnode(deep[u]+1);
memcpy(ch[nv],ch[v],sizeof(ch[v]));
pa[nv]=pa[v]; pa[v]=pa[np]=nv;
while(u&&ch[u][w]==v) ch[u][w]=nv,u=pa[u];
}
}
last=np;
}
int sum[N],stk[N];
void topsort()
{
for (int i=0;i<=deep[last];i++) sum[i]=0;
for (int i=1;i<=tot;i++) sum[deep[i]]++;
for (int i=1;i<=deep[last];i++) sum[i]+=sum[i-1];
for (int i=1;i<=tot;i++) stk[sum[deep[i]]--]=i;
for (int i=tot;i>=2;i--) cnt[pa[stk[i]]]+=cnt[stk[i]];
}
bool vis[N];
bool fst[N];
char s[N];
char st[N];
int pre[N];
int pc[N];
int bfs(int S)
{
queue<int>Q;
vis[S]=1;
Q.push(S);
while(!Q.empty())
{
int u=Q.front(); Q.pop();
for (int w=0;w<26;w++)
{
int v=ch[u][w];
if (v&&fst[v]&&!vis[v])
{
pre[v]=u;
pc[v]=w;
if (cnt[v]==0) return v;
vis[v]=1;
Q.push(v);
}
}
}
return -1;
}
int main()
{
int t; scanf("%d",&t);
for (int cas=1;cas<=t;cas++)
{
init();
int n; scanf("%d",&n);
scanf("%s",st+1);
for (int i=1;st[i];i++) insert(st[i]-'a');
for (int i=2;i<=n;i++)
{
scanf("%s",s+1);
insert(26); cnt[last]=1;
for (int j=1;s[j];j++)
insert(s[j]-'a'),cnt[last]=1;
}
topsort();
for (int i=1;i<=tot;i++) vis[i]=fst[i]=0;
int now=1;
for (int i=1;st[i];i++)
{
now=ch[now][st[i]-'a'];
int tmp=now;
while(tmp&&!fst[tmp]) fst[tmp]=1,tmp=pa[tmp];
}
printf("Case #%d: ",cas);
int ret=bfs(1);
if (ret!=-1)
{
int cnt=0;
for (int i=ret;i!=1;i=pre[i]) s[++cnt]=pc[i]+'a';
for (int i=cnt;i>=1;i--) printf("%c",s[i]);
printf("\n");
}
else printf("Impossible\n");
}
}
后缀自动机求字符串s1以i结尾的子串和s2到sn连接起来的串的最长公共子串，这个子串再向左延伸一个字符就是以i结尾的最短的只在s1中出现的子串。求出答案后暴力找字典序最小的串，要是答案太多可能会超时，然而数据没有卡这个时间。
Time：358ms
#include<bits/stdc++.h>
using namespace std;
const int N=600005;
int tot,root,last;
int pa[N],deep[N],ch[N][27],cnt[N];
int newnode(int _deep)
{
tot++;
memset(ch[tot],0,sizeof(ch[tot]));
deep[tot]=_deep;
cnt[tot]=0;
return tot;
}
void init()
{
tot=0;
root=newnode(0);
last=root;
}
void insert(int w)
{
int np=newnode(deep[last]+1);
int u=last;
while(u&&!ch[u][w]) ch[u][w]=np,u=pa[u];
if (!u) pa[np]=root;
else
{
int v=ch[u][w];
if (deep[u]+1==deep[v]) pa[np]=v;
else
{
int nv=newnode(deep[u]+1);
memcpy(ch[nv],ch[v],sizeof(ch[v]));
pa[nv]=pa[v]; pa[v]=pa[np]=nv;
while(u&&ch[u][w]==v) ch[u][w]=nv,u=pa[u];
}
}
last=np;
}
int sum[N],stk[N];
void topsort()
{
for (int i=0;i<=deep[last];i++) sum[i]=0;
for (int i=1;i<=tot;i++) sum[deep[i]]++;
for (int i=1;i<=deep[last];i++) sum[i]+=sum[i-1];
for (int i=1;i<=tot;i++) stk[sum[deep[i]]--]=i;
for (int i=tot;i>=2;i--) cnt[pa[stk[i]]]+=cnt[stk[i]];
}
char s[N];
char st[N];
int f[N];
bool cmp(int p1,int p2,int len)
{
for (int i=0;i<len;i++)
if (st[p1+i]!=st[p2+i]) return st[p1+i]<st[p2+i];
return 1;
}
int main()
{
int t; scanf("%d",&t);
for (int cas=1;cas<=t;cas++)
{
init();
int n; scanf("%d",&n);
scanf("%s",st+1);
for (int i=2;i<=n;i++)
{
scanf("%s",s+1);
for (int j=1;s[j];j++)
insert(s[j]-'a');
insert(26);
}
int now=root,step=0;
int ans=N;
for (int i=1;st[i];i++)
{
while(now&&!ch[now][st[i]-'a']) now=pa[now];
if (!now) now=1,step=0;
else step=deep[now]+1,now=ch[now][st[i]-'a'];
f[i]=step;
if (i-f[i]>0) ans=min(ans,f[i]);
}
printf("Case #%d: ",cas);
if (ans==N) printf("Impossible\n");
else
{
int id=0;
for (int i=1;st[i];i++)
if (i-f[i]>0&&f[i]==ans)
{
if (id==0||cmp(i-ans,id-ans,ans+1)) id=i;
}
for (int i=id-f[id];i<=id;i++) printf("%c",st[i]);
printf("\n");
}
}
}
后缀数组+二分答案，每次判断当前前缀相同的块里是否有s1的后缀并且没有其它串的后缀
Time：483ms
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=300005;
int a[N];
char s[N];
int pos,cut;
struct suffixarray
{
int sa[N],rk[N],h[N];
int cnt[N],sa2[N],rk2[N];
int rlen[N];
int n;
bool cmp(int i,int j,int len)
{
if (rk2[i]==rk2[j]&&rk2[i+len]==rk2[j+len]) return 0;
return 1;
}
void make(int *s,int len)
{
s[len+1]=-1; //按情况修改
n=len;
int m=60000; //按情况修改
for (int i=0;i<=m;i++) cnt[i]=0;
for (int i=1;i<=n;i++) cnt[s[i]]++;
for (int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
for (int i=n;i>=1;i--) sa[cnt[s[i]]--]=i;
int k=1; rk[sa[1]]=1;
for (int i=2;i<=n;i++)
{
if (s[sa[i]]!=s[sa[i-1]]) k++;
rk[sa[i]]=k;
}
rk2[n+1]=0;
for (int j=1;k<n&&j<=n;j*=2)
{
int tot=0;
for (int i=n-j+1;i<=n;i++) sa2[++tot]=i;
for (int i=1;i<=n;i++)
if (sa[i]>j) sa2[++tot]=sa[i]-j;
m=k;
for (int i=1;i<=m;i++) cnt[i]=0;
for (int i=1;i<=n;i++) cnt[rk[i]]++;
for (int i=2;i<=m;i++) cnt[i]+=cnt[i-1];
for (int i=n;i>=1;i--) sa[ cnt[rk[sa2[i]]]-- ]=sa2[i];
for (int i=1;i<=n;i++) rk2[i]=rk[i];
k=1; rk[sa[1]]=1;
for (int i=2;i<=n;i++)
{
if (cmp(sa[i],sa[i-1],j)) k++;
rk[sa[i]]=k;
}
}
for (int i=1;i<=n;i++)
{
if (rk[i]==1)
{
h[rk[i]]=0; //这里很容易错
continue;
}
k=h[rk[i-1]];
if (k>0) k--;
int j=sa[rk[i]-1];
while(s[i+k]==s[j+k]) k++;
h[rk[i]]=k;
}
}
void show()
{
printf("\n");
for (int i=1;i<=n;i++)
{
for (int j=sa[i];j<=n;j++)
printf("%c",char(a[j]));
printf(" %d\n",h[i]);
}
}
int idx;
bool check(int len)
{
bool hv1=0,hv2=0;
for (int i=1;i<=n;i++)
{
if (h[i]<len)
{
if (hv1&&!hv2)
{
idx=sa[i-1];
return 1;
}
hv1=hv2=0;
if (rlen[sa[i]]>=len)
{
if (sa[i]<cut) hv1=1;
else hv2=1;
}
}
else
{
if (sa[i]<cut) hv1=1;
else hv2=1;
}
}
return 0;
}
void solve(int *s)
{
int tmp=n;
for (int i=n;i>=1;i--)
{
if (s[i]>'z') tmp=i,rlen[i]=0;
else rlen[i]=tmp-i;
}
int l=1,r=cut;
while(l<r)
{
int mid=(l+r)/2;
if (!check(mid)) l=mid+1;
else r=mid;
}
if (l==cut) printf("Impossible\n");
else
{
check(l);
for (int i=idx;i<idx+l;i++)
printf("%c",char(s[i]));
printf("\n");
}
}
}SA;
int main()
{
int t; scanf("%d",&t);
for (int cas=1;cas<=t;cas++)
{
int n; scanf("%d",&n);
pos=0;
for (int i=1;i<=n;i++)
{
scanf("%s",s+1);
for (int j=1;s[j];j++)
a[++pos]=s[j];
a[++pos]='z'+i;
if (i==1) cut=pos;
}
SA.make(a,pos);
printf("Case #%d: ",cas);
//SA.show();
SA.solve(a);
}
}
