题目链接：
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | #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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | #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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 | #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); }} |
