bzoj 1396: 识别子串【SAM+线段树】

建个SAM，符合要求的串显然是|right|1的节点多代表的串，设si[i]为right集合大小，p[i]为right最大的r点，这些都可以建出SAM后再parent树上求得

然后对弈si[i]1的点，考虑它所代表的串是s(p[i]-dis[i]+1,p[i])~s(p[i]-dis[fa[i]],p[i])，然后对于p[i]-dis[i]+1<=x<=p[i]-dis[fa[i]]，对x的答案的贡献是p[i]-x+1，带着-x不好做所以最后再-x，也就是贡献p[i]+1；对于p[i]-dis[fa[i]]<=x<=p[i]，贡献是dis[fa[i]]+1（因为再小就重复了），所以建两棵线段树分别存两种贡献，最后取min即可

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=200005;

int n,fa[N],ch[N][27],dis[N],con=1,cur=1,la,p[N],c[N],a[N],si[N];

char s[N];

struct xds

{

	int l,r,mn,lz;

};

struct wk

{

	xds t[N<<2];

	void pd(int ro)

	{

		if(t[ro].lz!=1e9)

		{

			t[ro<<1].mn=min(t[ro<<1].mn,t[ro].lz);

			t[ro<<1].lz=min(t[ro<<1].lz,t[ro].lz);

			t[ro<<1|1].mn=min(t[ro<<1|1].mn,t[ro].lz);

			t[ro<<1|1].lz=min(t[ro<<1|1].lz,t[ro].lz);

			t[ro].lz=1e9;

		}

	}

	void build(int ro,int l,int r)

	{

		t[ro].l=l,t[ro].r=r,t[ro].mn=1e9,t[ro].lz=1e9;

		if(l==r)

			return;

		int mid=(l+r)>>1;

		build(ro<<1,l,mid);

		build(ro<<1|1,mid+1,r);

	}

	void update(int ro,int l,int r,int v)

	{

		if(t[ro].l==l&&t[ro].r==r)

		{

			t[ro].mn=min(t[ro].mn,v);

			t[ro].lz=min(t[ro].lz,v);

			return;

		}

		pd(ro);

		int mid=(t[ro].l+t[ro].r)>>1;

		if(r<=mid)

			update(ro<<1,l,r,v);

		else if(l>mid)

			update(ro<<1|1,l,r,v);

		else

			update(ro<<1,l,mid,v),update(ro<<1|1,mid+1,r,v);

		t[ro].mn=min(t[ro<<1].mn,t[ro<<1|1].mn);

	}

	int ques(int ro,int p)

	{

		if(t[ro].l==t[ro].r)

			return t[ro].mn;

		pd(ro);

		int mid=(t[ro].l+t[ro].r)>>1;

		if(p<=mid)

			return ques(ro<<1,p);

		else

			return ques(ro<<1|1,p);

	}

}t1,t2;

void ins(int c,int id)

{

	la=cur,dis[cur=++con]=id,p[cur]=id,si[cur]=1;

	int p=la;

	for(;p&&!ch[p][c];p=fa[p])

		ch[p][c]=cur;

	if(!p)

		fa[cur]=1;

	else

	{

		int q=ch[p][c];

		if(dis[q]==dis[p]+1)

			fa[cur]=q;

		else

		{

			int nq=++con;

			dis[nq]=dis[p]+1;

			memcpy(ch[nq],ch[q],sizeof(ch[q]));

			fa[nq]=fa[q];

			fa[q]=fa[cur]=nq;

			for(;ch[p][c]==q;p=fa[p])

				ch[p][c]=nq;

		}

	}

}

int main()

{

	scanf("%s",s+1);

	n=strlen(s+1);

	for(int i=1;i<=n;i++)

		ins(s[i]-'a',i);

	t1.build(1,1,n),t2.build(1,1,n);

	for(int i=1;i<=con;i++)

		c[dis[i]]++;

	for(int i=1;i<=n;i++)

		c[i]+=c[i-1];

	for(int i=1;i<=con;i++)

		a[c[dis[i]]--]=i;

	for(int i=con;i>=1;i--)

		si[fa[a[i]]]+=si[a[i]],p[fa[a[i]]]=max(p[fa[a[i]]],p[a[i]]);

	// for(int i=1;i<=con;i++)

		// cerr<<si[i]<<" "<<p[i]<<endl;

	for(int i=1;i<=con;i++)

		if(si[i]==1)

			t1.update(1,p[i]-dis[i]+1,p[i]-dis[fa[i]],p[i]+1),t2.update(1,p[i]-dis[fa[i]],p[i],dis[fa[i]]+1);

	for(int i=1;i<=n;i++)

		printf("%d\n",min(t1.ques(1,i)-i,t2.ques(1,i)));

	return 0;

}

巴特西

bzoj 1396: 识别子串【SAM+线段树】

最新文章

热门文章