作者:黄家驹1994 | 来源:互联网 | 2023-05-18 15:31
题目大意:
求出字典序最小,重复次数最多,的子串。
思路分析:
RMQ + height 数组可以求出任意两个后缀的lcp
我们枚举答案字符串的重复的长度。
如果这个字符串的长度为 l ,而且这个字符串出现过两次或两次以上
那么你会发现在原串中 str[0] str[l] str[2*l] ....肯定有相邻的两个被包含在重复的串中。
我们求出这两个相邻的后缀的lcp
我们上面仅仅说的是被包含在重复的串中,但并不一定就是以 str[0], str[l],str[2*l]....为起点的。
那我们就要往前去寻找这个起点。
也不是往前枚举,可以发现只要往前移动 l-lcp%l 个位置。
比如。
xbcabcab
当 l = 3 的时候
你找到了
ab
abcab
发现 lcp = 2,然后往前减去一个 l-lcp%l ,结果cab和cabcab的lcp 变成了3
也就是说往前寻找可以再补齐一个周期。
再讨论字典序最小的问题。
在sa中找到的第一个,满足最长的重复次数和长度的也就是字典序最小的了。
#include
#include
#include
#include
#include
#define maxn 100005
using namespace std;
char str[maxn];
int sa[maxn],t1[maxn],t2[maxn],c[maxn],n;
void suffix(int m)
{
int *x=t1,*y=t2;
for(int i=0; i=0; i--)sa[--c[x[i]]]=i;
for(int k=1; k<=n; k<<=1)
{
int p=0;
for(int i=n-k; i=k)y[p++]=sa[i]-k;
for(int i=0; i=0; i--)sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=1;
x[sa[0]]=0;
for(int i=1; i=n)break;
m=p;
}
}
int rank[maxn],height[maxn];
void getheight()
{
int k=0;
for(int i=0; ir)swap(l,r);
l++;
int k=floor(log(r-l+1.0)/log(2.0));
return min(f[l][k],f[r+1-(1<=l && lcp%l)
{
if(RMQ(rank[st-l],rank[st])>=lcp)
repeat++;
}
if(repeat>Max)
{
Max=repeat;
top=0;
ans[top++]=l;
}
else if(repeat==Max)ans[top++]=l;
}
}
int len=-1,st;
for(int i=1;i=(Max-1)*ans[j])
{
len=ans[j];
st=sa[i];
break;
}
}
printf("Case %d: ",cas++);
for(int i=st;i
POJ 3693 Maximum repetition substring (后缀数组),,
POJ 3693 Maximum repetition substring (后缀数组)