XV.Annihilate
我当年为什么会手贱开这卡常大毒瘤题呀
思路1. 用vector存下每个字符串在后缀排序后的下标，然后每次枚举两个串，用一个vector里面的数在另一个里面two-pointers找到它两侧的数，然后用ST表求LCP。
时间复杂度\(O\Big(\sum|S|(\log\sum|S|+n^2)\Big)\)，空间复杂度\(O(n\log n)\)，光荣MLE。
代码：
#include<bits/stdc++.h>
using namespace std;
int all,id[1001000],res[100][100];
namespace Suffix_Array{
const int N=1001000;
int x[N],y[N],sa[N],ht[N],rk[N],buc[N],n,m;
char s[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(j+k<n&&i+k<n&&s[j+k]==s[i+k])k++;
ht[rk[i]]=k;
}
}
}
using namespace Suffix_Array;
vector<int>v[60];
int mn[1001000][20],LG[1001000];
int LCP(int l,int r){//get the LCP of suffix l and r;
l++;
int k=LG[r-l+1];
return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
int main(){
scanf("%d",&all);
for(int i=1;i<=all;i++){
scanf("%s",s+n);
m=strlen(s+n);
for(int j=n;j<n+m;j++)id[j]=i;
n+=m;
s[n++]=i;
}
m='z';
SA();
for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
for(int i=1;i<n;i++)mn[i][0]=ht[i];
for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
for(int i=0;i<n;i++)if(id[sa[i]])v[id[sa[i]]].push_back(i);
for(int i=1;i<=all;i++)for(int j=i+1;j<=all;j++){
for(int a=0,b=0;a<v[i].size();a++){
while(b<v[j].size()&&v[i][a]>v[j][b])b++;
if(b<v[j].size())res[i][j]=max(res[i][j],LCP(v[i][a],v[j][b]));
if(b)res[i][j]=max(res[i][j],LCP(v[j][b-1],v[i][a]));
}
}
for(int i=1;i<=all;i++){for(int j=1;j<=all;j++)if(i!=j)printf("%d ",res[min(i,j)][max(i,j)]);puts("");}
return 0;
}
思路2. 用单调队列求LCP
大体思路和上题一致，只不过换用单调队列求LCP。
时间复杂度\(O\Big(\sum|S|(\log\sum|S|+n^2)\Big)\)，光荣TLE。
代码：
#include<bits/stdc++.h>
using namespace std;
int all,id[1001000],res[100][100];
namespace Suffix_Array{
const int N=1001000;
int x[N],y[N],sa[N],ht[N],rk[N],buc[N],n,m;
char s[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(j+k<n&&i+k<n&&s[j+k]==s[i+k])k++;
ht[rk[i]]=k;
}
}
}
using namespace Suffix_Array;
vector<int>v[60];
int main(){
scanf("%d",&all);
for(int i=1;i<=all;i++){
scanf("%s",s+n);
m=strlen(s+n);
for(int j=n;j<n+m;j++)id[j]=i;
n+=m;
s[n++]=i;
}
m='z';
SA();
for(int i=1;i<=all;i++)v[i].push_back(i);
for(int i=0;i<n;i++)if(id[sa[i]])v[id[sa[i]]].push_back(i);
for(int i=1;i<=all;i++)for(int j=i+1;j<=all;j++){
deque<int>p,q;
for(int a=1,b=0;a<v[i].size();a++){
for(int k=v[i][a-1]+1;k<=v[i][a];k++){
while(!p.empty()&&ht[p.back()]>=ht[k])p.pop_back();
p.push_back(k);
}
while(b<v[j].size()&&v[i][a]>v[j][b]){
while(!p.empty()&&p.front()<=v[j][b])p.pop_front();
b++;
if(b==v[j].size())break;
for(int k=v[j][b-1]+1;k<=v[j][b];k++){
while(!q.empty()&&ht[q.back()]>=ht[k])q.pop_back();
q.push_back(k);
}
}
while(!q.empty()&&q.front()<=v[i][a])q.pop_front();
if(!p.empty())res[i][j]=max(res[i][j],ht[p.front()]);
if(!q.empty())res[i][j]=max(res[i][j],ht[q.front()]);
}
}
for(int i=1;i<=all;i++){for(int j=1;j<=all;j++)if(i!=j)printf("%d ",res[min(i,j)][max(i,j)]);puts("");}
return 0;
}
思路3.正解
我们设一个\(las_i\)表示当前位置到上一个来自\(i\)串的后缀的区间中的\(\min ht_x\)。到了每一个位置\(O(n)\)地遍历\(las\)数组更新并计算答案。复杂度\(O\Big(\sum|S|\log(\sum|S|+n)\Big)\)，可以通过。
但是这题卡常强烈吐槽！
代码（开O2通过）：
#include<bits/stdc++.h>
using namespace std;
int all,id[1010000],res[100][100],las[100];
namespace Suffix_Array{
const int N=1010000;
int x[N],y[N],sa[N],ht[N],rk[N],buc[N],n,m,s[N];
void SA(){
for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++)y[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=1;i<=n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);
x[sa[1]]=num=1;
for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
if(num>=n)break;
m=num;
}
for(int i=1;i<=n;i++)rk[sa[i]]=i;
for(int i=1,k=0;i<=n;i++){
if(rk[i]==1)continue;
if(k)k--;
int j=sa[rk[i]-1];
while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k])k++;
ht[rk[i]]=k;
}
}
}
using namespace Suffix_Array;
char str[1001000];
int main(){
scanf("%d",&all);
for(int i=1;i<=all;i++){
scanf("%s",str);
m=strlen(str);
for(int j=0;j<m;j++)n++,s[n]=str[j]-'a'+1,id[n]=i;
s[++n]=i+26;
}
m=all+26;
SA();
// for(int i=1;i<=n;i++)printf("%d ",s[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",rk[i]);puts("");
for(int i=2;i<=n;i++){
for(int j=1;j<=all;j++)las[j]=min(las[j],ht[i]);
las[id[sa[i-1]]]=ht[i];
for(int j=1;j<=all;j++)res[j][id[sa[i]]]=max(res[j][id[sa[i]]],las[j]);
}
for(int i=1;i<=all;i++){for(int j=1;j<=all;j++)if(i!=j)printf("%d ",max(res[i][j],res[j][i]));puts("");}
return 0;
}