传送门
题意： XX在进行字符串研究的时候，遇到了一个十分棘手的问题。 在这个问题中，给定一个字符串S，与一个整数K，定义S的子串T=S(i, j)是关于第K位的识别子串，满足以下两个条件： 1、i≤K≤j。 2、子串T只在S中出现过一次。 例如，S=“banana”，K=5，则关于第K位的识别子串有"nana"，“anan”，“anana”，“nan”，“banan"和"banana”。 现在，给定S，XX希望知道对于S的每一位，最短的识别子串长度是多少，请你来帮助他。
题解： 证明自己学过后缀数组 我们可以求出每一位pos开始的后缀的最短前缀，即 f = m a x ( h e i g h t [ r a n k [ i ] ] , h e i g h t [ r a n k [ i ] + 1 ] ) + 1 f=max(height[rank[i]],height[rank[i]+1])+1 f=max(height[rank[i]],height[rank[i]+1])+1. 简单证明一下（因为我看到的后缀数组的做法好像都没有证明，似乎对我这个蒟蒻不太友好…），我们知道rank的定义是某个后缀在所有后缀中的排名，height的定义是suffix(sa[i-1])和suffix(sa[i])的最长公共前缀，也就是两个排名相邻的后缀的最长公共前缀。那么上式的意思就是这一位和相邻两个后缀的最长公共前缀+1，所以就不会有重复。 如果 p o s + f − 1 ≤ n pos+f-1\le n pos+f−1≤n，那么 [ p o s , p o s + f − 1 ] [pos,pos+f-1] [pos,pos+f−1]的答案就与 f f f取min；如果 p o s + f − 1 < n pos+f-1\lt n pos+f−1<n，那么 [ p o s + f , n ] [pos+f,n] [pos+f,n]上的位置i上的答案就与 i − p o s + 1 i-pos+1 i−pos+1取min。 然后用两棵线段树分别维护f和1-pos的最小值即可。
代码：
#include<cstdio> #include<cstring> #include<algorithm> #define maxn 500005 #define N 233 #define INF 0x3f3f3f3f using namespace std; int n,arr[4][maxn],*sa,*nsa,*rk,*nrk,b[maxn],height[maxn]; char a[maxn]; struct segtree { int val[maxn*4]; void Build() { memset(val,0x3f,sizeof(val)); } void Modify(int i,int l,int r,int ql,int qr,int d) { if(ql<=l&&r<=qr) { val[i]=min(val[i],d); return; } int mid=(l+r)>>1; if(ql<=mid) Modify(i<<1,l,mid,ql,qr,d); if(qr>mid) Modify(i<<1|1,mid+1,r,ql,qr,d); } int Query(int i,int l,int r,int p) { if(l==r) return val[i]; int mid=(l+r)>>1; if(p<=mid) return min(val[i],Query(i<<1,l,mid,p)); else return min(val[i],Query(i<<1|1,mid+1,r,p)); } }tree1,tree2; void cal_sa() { sa=arr[0],nsa=arr[1],rk=arr[2],nrk=arr[3]; memset(b,0,sizeof(b)); for(int i=1;i<=n;i++) b[a[i]]++; for(int i=1;i<N;i++) b[i]+=b[i-1]; for(int i=1;i<=n;i++) sa[b[a[i]]--]=i; for(int i=1;i<=n;i++) { rk[sa[i]]=rk[sa[i-1]]; if(a[sa[i]]!=a[sa[i-1]]) rk[sa[i]]++; } for(int k=1;rk[sa[n]]<n&&k<n;k*=2) { for(int i=1;i<=n;i++) b[rk[sa[i]]]=i; for(int i=n;i;i--) if(sa[i]>k) nsa[b[rk[sa[i]-k]]--]=sa[i]-k; for(int i=n-k+1;i<=n;i++) nsa[b[rk[i]]--]=i; for(int i=1;i<=n;i++) { nrk[nsa[i]]=nrk[nsa[i-1]]; if(rk[nsa[i]]!=rk[nsa[i-1]]||rk[nsa[i]+k]!=rk[nsa[i-1]+k]) nrk[nsa[i]]++; } swap(sa,nsa); swap(rk,nrk); } } void cal_height() { for(int i=1,k=0;i<=n;i++) { if(rk[i]==1) height[1]=0; else { if(k>0) k--; for(int j=sa[rk[i]-1];i+k<=n&&j+k<=n&&a[i+k]==a[j+k];k++); height[rk[i]]=k; } } } int main() { scanf("%s",a+1); n=strlen(a+1); cal_sa(); cal_height(); tree1.Build(); tree2.Build(); for(int i=1;i<=n;i++) { int cur=max(height[rk[i]],height[rk[i]+1])+1; if(i+cur-1<=n) tree1.Modify(1,1,n,i,i+cur-1,cur); if(i+cur<=n) tree2.Modify(1,1,n,i+cur,n,1-i); } for(int i=1;i<=n;i++) printf("%d\n",min(tree1.Query(1,1,n,i),tree2.Query(1,1,n,i)+i)); }