GYM-101194F Mr. Panda and Fantastic Beasts 后缀数组套路
题意
给定(n)个字符串，找出第一个字符串的最短的子串，使得其不存在任何其他字符串中
[1 leq T leq42\
2 leq N leq 50000\
N leq sum|S_i| leq 250000
]
分析
可以说是比较套路的后缀数组应用
1.用没出现过的字符拼接(n)个字符串
2.求出拼接的字符串的后缀数组和Height数组
3.将问题转化为判定性问题：二分答案长度
4.扫描Height数组，根据长度对Height数组分组，若存在某个组为单独的字符串且属于第一个字符串且其长度>=二分长度，返回true
顺便嫖一波封装好的SA模板
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
ll rd(){
ll x = 0;
int f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x =x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
ll ksm(ll a,ll b,ll m){
ll ans = 1;
ll base = a;
while(b){
if(b & 1) {
ans *= base;
ans %= m;
}
base *= base;
base %= m;
b >>= 1;
}
return ans;
}
const int maxn = 350005;
struct SA{
char s[maxn];
int q,len;
int rk[2][maxn],sa[maxn],h[maxn],w[maxn],now,m,n,vis[50005],pos;
int rmq[maxn][20],lg[maxn],bel[maxn];
void getsa(int z,int &m) {
int x=now,y=now^=1;
for(int i=1; i<=z; i++) rk[y][i]=n-i+1;
for(int i=1,j=z; i<=n; i++)
if(sa[i]>z) rk[y][++j]=sa[i]-z;
for(int i=1; i<=m; i++) w[i]=0;
for(int i=1; i<=n; i++) w[rk[x][rk[y][i]]]++;
for(int i=1; i<=m; i++) w[i]+=w[i-1];
for(int i=n; i>=1; i--) sa[w[rk[x][rk[y][i]]]--]=rk[y][i];
for(int i=m=1; i<=n; i++)
{
int *a=rk[x]+sa[i],*b=rk[x]+sa[i-1];
rk[y][sa[i]]=*a==*b&&*(a+z)==*(b+z)?m-1:m++;
}
}
void getsa(int m){
now=rk[1][0]=sa[0]=s[0]=0;
for(int i=1; i<=m; i++) w[i]=0;
for(int i=1; i<=n; i++) w[s[i]]++;
for(int i=1; i<=m; i++) rk[1][i]=rk[1][i-1]+(bool)w[i];
for(int i=1; i<=m; i++) w[i]+=w[i-1];
for(int i=1; i<=n; i++) rk[0][i]=rk[1][s[i]];
for(int i=1; i<=n; i++) sa[w[s[i]]--]=i;
rk[1][n+1]=rk[0][n+1]=0;
for(int x=1,y=rk[1][m]; x<=n&&y<=n; x<<=1) getsa(x,y);
for(int i=1,j=0; i<=n; h[rk[now][i++]]=j?j--:j)
{
if(rk[now][i]==1) continue;
int k=n-max(sa[rk[now][i]-1],i);
while(j<=k&&s[sa[rk[now][i]-1]+j]==s[i+j]) ++j;
}
}
void getrmq(){
h[n+1]=h[1]=lg[1]=0;
for(int i=2; i<=n; i++)
rmq[i][0]=h[i],lg[i]=lg[i>>1]+1;
for(int i=1; (1<<i)<=n; i++){
for(int j=2; j<=n; j++){
if(j+(1<<i)>n+1) break;
rmq[j][i]=min(rmq[j][i-1],rmq[j+(1<<i-1)][i-1]);
}
}
}
int lcp(int x,int y) {
int l=min(rk[now][x],rk[now][y])+1,r=max(rk[now][x],rk[now][y]);
return min(rmq[l][lg[r-l+1]],rmq[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
bool check(int x) {
vector<int> g;
int cnt=0;
for(int i=1;i<=n;i++){
if(h[i]>=x){
if(!vis[bel[sa[i]]]) vis[bel[sa[i]]]=1,cnt++,g.push_back(bel[sa[i]]);
if(!vis[bel[sa[i-1]]]) vis[bel[sa[i-1]]]=1,cnt++,g.push_back(bel[sa[i-1]]);
}
else{
if(cnt <= 1 && bel[sa[i-1]] == 1 && len - sa[i - 1] + 1 >= x) {vis[1] = 0;pos = sa[i - 1];return 1;}
cnt=0;
for(auto it:g)
vis[it]=0;
g.clear();
}
}
if(cnt <= 1 && bel[sa[n]] == 1 && len - sa[n] + 1 >= x) {
vis[1] = 0;
return 1;
}
for(auto it:g)
vis[it]=0;
return 0;
}
}sa;
char ch[maxn];
int main(){
int T = rd();
int kase = 0;
while(T--){
sa.len = 0;
char q = '$';
int n = rd();
int cur = 0;
for(int i = 0;i < n;i++){
scanf("%s",ch);
int l = strlen(ch);
for(int j = 0;j < l;j++){
sa.s[++cur] = ch[j],sa.bel[cur] = i + 1;
if(!i) sa.len++;
}
sa.s[++cur] = q;
}
sa.n = cur;
sa.getsa(55000);
int l = 1,r = sa.len,ans = 0;
while(l <= r){
int mid = l + r >> 1;
if(sa.check(mid)) ans = mid,r = mid - 1;
else l = mid + 1;
}
printf("Case #%d: ",++kase);
if(!ans) {
puts("Impossible");
}
else{
for(int i = sa.pos;i < sa.pos + l;i++)
printf("%c",sa.s[i]);
puts("");
}
}
}