原文链接http://www.cnblogs.com/zhouzhendong/p/9004467.html
题目传送门 - BZOJ1396
题意
给定一个字符串$s$，$|s|\leq 10^5$。
对于$s$的每一个位置，求$s$的包含该位置的、仅在$s$中出现一次的连续子串的最短长度。
题解
考虑先对于$s$构建一个后缀自动机。
由于我们要考虑的串是只能在$s$中出现一次的。
所以我们先基数排序，然后通过$fa$指针计算每一个节点的$Right$集合。
只出现一次的就是$Right$集合大小为$1$的。
对于$Right$大小为$1$的节点$i$，首先我们得知$s[Right(i)-Max(i)+1\cdots Right(i)]$是只出现一次的，所以我们开个线段树，直接标记永久化，让$Right(i)-Max(i)+1\cdots Right(i)$的答案对于$Max(i)$取个$\min$。又考虑到$s[Right(i)-j+1\cdots Right(i)|Max(i)\geq j > Max(fa(i))]$也是只出现一次的，只不过区间对某一个定值取$\min$改成了对等差数列取$\min$而已。
于是只需要开两棵标记永久化的线段树即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100005;
int n,Min[N<<2],Min2[N<<2];
int root=1,size=1,last=1;
int plast[N],tax[N],totend[N<<1],id[N<<1];
char s[N];
struct SAM{
int Next[26],fa,Max;
}t[N<<1];
void extend(int c){
int p=last,np=++size,q,nq;
t[np].Max=t[p].Max+1;
for (;!t[p].Next[c];p=t[p].fa)
t[p].Next[c]=np;
q=t[p].Next[c];
if (t[q].Max==t[p].Max+1)
t[np].fa=q;
else {
nq=++size;
t[nq]=t[q],t[nq].Max=t[p].Max+1;
t[q].fa=t[np].fa=nq;
for (;t[p].Next[c]==q;p=t[p].fa)
t[p].Next[c]=nq;
}
last=np;
}
void build(int rt,int L,int R){
Min[rt]=n,Min2[rt]=n*2;
if (L==R)
return;
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
build(ls,L,mid);
build(rs,mid+1,R);
}
void update1(int rt,int L,int R,int xL,int xR,int v){
if (L>xR||xL>R)
return;
if (xL<=L&&R<=xR){
Min[rt]=min(Min[rt],v);
return;
}
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
update1(ls,L,mid,xL,xR,v);
update1(rs,mid+1,R,xL,xR,v);
}
void update2(int rt,int L,int R,int xL,int xR,int v){
if (L>xR||xL>R)
return;
if (xL<=L&&R<=xR){
Min2[rt]=min(Min2[rt],v);
return;
}
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
update2(ls,L,mid,xL,xR,v);
update2(rs,mid+1,R,xL,xR,v-(mid-L+1));
}
int query(int rt,int L,int R,int x){
if (L==R)
return min(Min[rt],Min2[rt]);
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
if (x<=mid)
return min(query(ls,L,mid,x),min(Min[rt],Min2[rt]-(x-L)));
else
return min(query(rs,mid+1,R,x),min(Min[rt],Min2[rt]-(x-L)));
}
int main(){
scanf("%s",s+1);
n=strlen(s+1);
t[0].Max=-1;
for (int i=0;i<26;i++)
t[0].Next[i]=1;
for (int i=1;i<=n;i++)
extend(s[i]-'a'),plast[i]=last;
for (int i=1;i<=size;i++)
tax[t[i].Max]++;
for (int i=1;i<=n;i++)
tax[i]+=tax[i-1];
for (int i=1;i<=size;i++)
id[tax[t[i].Max]--]=i,totend[i]=-1;
for (int i=1;i<=n;i++)
totend[plast[i]]=i;
for (int i=size;i>=1;i--){
int &fa=totend[t[id[i]].fa],&now=totend[id[i]];
fa=fa==-1?now:-2;
}
build(1,1,n);
for (int i=2;i<=size;i++){
if (totend[i]<0)
continue;
int p3=totend[i],p2=p3-t[i].Max+1,p1=p3-t[t[i].fa].Max;
update1(1,1,n,p1,p3,t[t[i].fa].Max+1);
update2(1,1,n,p2,p1,t[i].Max+(p2-1));
}
for (int i=1;i<=n;i++)
printf("%d\n",query(1,1,n,i));
return 0;
}