本文共 2479 字，大约阅读时间需要 8 分钟。

求出现次数恰好为$k$的所有子串中,出现次数最多的长度

这个题用$SAM$就太赖皮了,每个点的$siz$值就是出现i+的次数…

所以这里用后缀数组来写

尺取一个长度为$k-1$的$height$区间,设区间最小值是$x$,尺取区间是$[i-k+2,i]$

那么说明在$i\in [i-k+1,i]$的所有$sa[i]$中,都出现过长$x$的这个前缀

如果$x$不出现在$sa[i-k]$和$sa[i+1]$,就是恰好出现$k$次

所以合法长度的下界是$max(height[i-k+1],height[i+1])$

合法长度的上界是$x$

问题就得到解,我们只需要知道所有区间长度为$k-1$的$height$区间最小值即可

这个可以$ST$表预处理,但是单调队列可以做到$O(n)$??

最后加一句所有写后缀数组的人都会口胡的话,使用$DC3$法预处理$height$数组整体复杂度达到$O(n)$

#include 
   
    using namespace std;const int maxn = 4e5+10;int height[maxn],sa[maxn],x[maxn],rk[maxn],y[maxn],c[maxn],n,m,k,cha[maxn];char a[maxn];void SA(){
   	m = 500; int las = max(n,m);	for(int i=0;i<=las+1;i++)	sa[i]=rk[i]=x[i]=y[i]=c[i]=height[i]=0;		for(int i=1;i<=n;i++)	c[x[i]=a[i]]++;	for(int i=1;i<=m;i++)	c[i] += c[i-1];	for(int i=n;i>=1;i--)	sa[c[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++)	c[i] = 0;		for(int i=1;i<=n;i++)	c[x[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], y[i] = 0;		swap(x,y);		num = 1, x[sa[1]] = 1;		for(int i=2;i<=n;i++)			x[sa[i]] = ( y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+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( i+k<=n&&j+k<=n&&a[i+k]==a[j+k] )	k++;		height[rk[i]] = k;	}}int head,tail,q[maxn];void init1(){
   	for(int i=2;i<=n;i++)	{
   		int l = max(height[i],height[i+1]), r = n-sa[i]+1;		if( l
    
     =head&&height[q[tail]]>=height[i] )	tail--;		q[++tail] = i;		if( i<=k )	continue;		//现在排除一些元素,使得区间长度小于等于k		while( i-q[head]+1>k )	head++;		int x = height[q[head]], mx = max( height[i-k],height[i+1] );//[i-k+1,i]		if( mx
     
      > t;	while( t-- )	{
   		scanf("%s%d",a+1,&k); n = strlen( a+1 );		SA();		if( k==1 )	init1();		else	init2();		for(int i=1;i<=n;i++)	cha[i] += cha[i-1];		int ans = -1, num = 1;		for(int i=1;i<=n;i++)		{
   			if( cha[i]>=num )	ans = i,num = cha[i];		}		for(int i=0;i<=n+1;i++)	cha[i] = 0;		printf("%d\n",ans);	}}
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/114434479 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！