china-final F Mr. Panda and Fantastic Beasts (后缀自动机+字典序最小的最短路）

题目链接：

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);
    }
}