题目链接：
https://www.cometoj.com/contest/68/problem/G?problem_id=3940
出题人给的题解： 我们知道，一个子串是字符串的后缀的前缀。 这就很自然地让我们想到了后缀数组。 我们可以将原串 T 与询问的字符串?1,?2 …??拼接构造出一个新字符 串， 我们令新字符串为 Tc?1??2??3?…???c 其中 c 为大于字符串中所有字符的特殊字符 我们在这个串上建立后缀数组，可以得到文本串的每个后缀与匹配串 之间的关系。 由于我们在每个询问串中加了 c，从这个询问串开始的位置的后缀的 排名就是这个询问串的排名。 按照字典序由大到小枚举后缀，记 mini为目前在 T 中的后缀的最小位 置。如果枚举到了某个 S 的开头，他的答案就是 mini。 要注意的是要保证这个串的终止位置也要在 T 中，否则答案就是 -1
DC3实现后缀数组代码：
https://paste.ubuntu.com/p/sRnDdkK94Y/
下边是基数排序实现的代码：
/* sa 小标从0到strlen(s)-1. 值从0到strlen(s)-1 */ #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+5; int sa[maxn],Rank[maxn],rank2[maxn],cnt[maxn],*x,*y,mxx[maxn]; int ans[maxn]; int Q[maxn]; int Slen[maxn]; void radix_sort(int n,int m){ memset(cnt,0,sizeof(cnt)); for(int i=0;i<n;i++) cnt[x[y[i]]]++; for(int i=1;i<m;i++) cnt[i]+=cnt[i-1]; for(int i=n-1;i>=0;i--) sa[--cnt[x[y[i]]]]=y[i]; } void get_sa(string s,int n){ int m=128; x=Rank,y=rank2; for(int i=0;i<n;i++) x[i]=s[i],y[i]=i; radix_sort(n,m); for(int len=1;len<n;len<<=1){ int p=0; for(int i=n-len;i<n;i++) y[p++]=i; for(int i=0; i<n; i++) if(sa[i]>=len) y[p++]=sa[i]-len; radix_sort(n,m); swap(x,y); x[sa[0]]=p=0; for(int i=1;i<n;i++){ if(y[sa[i-1]]==y[sa[i]]&&sa[i-1]+len<n&&sa[i]+len<n&&y[sa[i-1]+len]==y[sa[i]+len]) x[sa[i]]=p; else x[sa[i]]=++p; } m=p+1; if(m>=n) break; } for(int i=0;i<n;i++) Rank[i]=x[i]; } int main(){ memset(ans,-1,sizeof ans); string s; int q; cin>>q; cin>>s; int n=s.length(); s+='z'+1; for(int i=1;i<=q;i++){ Q[s.length()]=i; string ss; cin>>ss; Slen[i]=ss.length(); s+=ss; s+='z'+2; } int len=s.length(); get_sa(s,len); int minn=0x3f3f3f3f; for(int i=len-1;i>=0;i--){ if(sa[i]<n) minn=min(minn,sa[i]); else if(Q[sa[i]]&&minn+Slen[Q[sa[i]]]-1<n) ans[Q[sa[i]]]=minn; } for(int i=1;i<=q;i++){ printf("%d\n",ans[i]); } return 0; }
