luogu P5546 [POI2000]公共串

首先把这些串排成一排（中间用随便什么符号隔断一下），然后跑一遍后缀数组。

我们把这些后缀排序后，发现一段区间可以对答案有贡献当且仅当 \(n\) 个字符串的任意位置都在这个区间出现过，然后 \(two\_point\) 跑一遍，可以用你喜欢的数据结构维护 \(height\) 的最小值。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<deque>

using namespace std;

void Modify(int k,int l,int r,int x,int v);
const int N=1000000,INF=1<<30;
int Q,Min[N*4],add[N*4];
char s[N];
deque <int> q;
struct Suffix_Array
{
	char s[N];
	int n,m,x[N],y[N],sa[N],c[N],height[N],h[N],rev[N],bin[N],fuck[N],H[N];
	
	void Rsort()
	{
		for (int i=1;i<=m;i++) c[i]=0;
		for (int i=1;i<=n;i++) c[x[y[i]]]++;
		for (int i=1;i<=m;i++) c[i]+=c[i-1];
		for (int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i];
	}
	
	void Get_SA()
	{
		m=122;
		for (int i=1;i<=n;i++)
			x[i]=s[i],y[i]=i;
		Rsort();
		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;
			Rsort(),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;
		}
	}
	
	void Get_Height()
	{
		for (int i=1;i<=n;i++)
		{
			int tmp=max(0,h[i-1]-1),j,k;
			for (j=i+tmp,k=sa[x[i]-1]+tmp;s[j]==s[k]&&j<=n&&k<=n;j++,k++);
			h[i]=j-i;
		}
		for (int i=1;i<=n;i++)
			height[i]=h[sa[i]];
	}
	
	int Get_Ans()
	{
		if(Q==1)
			return n;
		Get_SA(),Get_Height();
//		printf("%d\n",n);
//		for (int i=1;i<=n;i++)
//			printf("%d ",height[i]);puts("");
		int cnt=0;
		for (int i=1;i<=n;i++)
			if(rev[sa[i]]!=0)
				fuck[++cnt]=rev[sa[i]];
		cnt=0;
		for (int i=1;i<=n;i++)
			if(rev[sa[i]]!=0)
				H[++cnt]=height[i];
		int i,sum=0;
		int flag=0;
		for (i=1;i<=cnt;i++)
		{
			sum+=(++bin[fuck[i]]==1)?1:0;
			if(flag!=1)
			{
				flag=1;
				continue;
			}
			Modify(1,0,n,H[i],1);
			if(sum==Q)
				break;
		}
		int l=1,r=i;
		while(bin[fuck[l]]>1)
			bin[fuck[l]]--,Modify(1,0,n,H[l+1],-1),l++;
		int ans=Min[1];
		for (i=i+1;i<=cnt;i++)
		{
			bin[fuck[i]]++;
			Modify(1,0,n,H[i],1);
			while(bin[fuck[l]]>1)
				Modify(1,0,n,H[l+1],-1),bin[fuck[l]]--,l++;
			ans=max(ans,Min[1]);
//			printf("%d %d\n",l,i);
		}
		return ans;
	}
}A;

void Modify(int k,int l,int r,int x,int v)
{
	if(l==r)
	{
		add[k]+=v;
		Min[k]=add[k]?l:INF;
		return;
	}
	int mid=l+r>>1;
	if(mid>=x)
		Modify(k<<1,l,mid,x,v);
	else
		Modify(k<<1|1,mid+1,r,x,v);
	Min[k]=min(Min[k<<1],Min[k<<1|1]);
}

void build(int k,int l,int r)
{
	Min[k]=INF;
	if(l==r)
		return;
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}

void init()
{
	scanf("%d",&Q);
	for (int i=1;i<=Q;i++)
	{
		scanf("%s",s+1);
		int len=strlen(s+1);
		for (int j=1;j<=len;j++)
			A.s[++A.n]=s[j],A.rev[A.n]=i;
		A.s[++A.n]=‘0‘+i;
	}
	build(1,0,A.n);
}

void work()
{
	printf("%d\n",A.Get_Ans());
}

int main()
{
	init();
	work();
	return 0;
}

luogu P5546 [POI2000]公共串

原文：https://www.cnblogs.com/With-penguin/p/13341972.html