字体颜色如何
字体颜色
SPOJ - REPEATS
题意
给出一个字符串，求重复次数最多的连续重复子串。
题解
引自论文-后缀数组——处理字符串的有力工具。
“S肯定包括了字符r[0], r[L], r[L * 2],r[L * 3], ……中的某相邻的两个”
由于当前S是有两个长度为L的连续重复子串拼接而成的，那意味着S[i]和S[i+L] ( 0≤i<L )必定是一样的字符
而这两个字符位置相差L
而字符r[0],r[L],r[L * 2],r[L * 3],......中相邻两个的位置差均为L
所以只须看字符r[L* i]和r[L* (i+1)]往前和
往后各能匹配到多远，记这个总长度为K，那么这里连续出现了K/L+1次。
这句就是枚举(r[l * i]),(r[l * (i+1)])，分别作为重复子串第一二个重复的串中的字符时，重复子串的重复次数可以是多少。
结合上面图中的数组更容易理解.
如果此时r[i * L]是第一个重复子串的首字符，这样直接用公共前缀[lcp(i * L ,L* (i+1))]k除以L并向下取整+1就可以得到最后结果。但如果r[i * L]如果不是首字符，这样算完之后结果就有可能偏小，因为r[i * L]前面可能还有少许字符也能看作是第一个重复子串里的。
于是，我们不妨先算一下，从r[i * L]开始，除匹配了k/L个重复子串，还剩余了几个字符，剩余的自然是k%L个字符。如果说r[i * L]的前面还有L-k%L个字符完成匹配的话，这样就相当于利用多余的字符还可以再匹配出一个重复子串，于是我们只要检查一下从r[i * L-(L-k%L)]和r[L * (i+1)-(L-k%L)]开始是否有L-k%L个字符能够完成匹配即可，也就是说去检查这两个后缀的最长公共前缀是否比L-k%L大即可。
当然如果公共前缀不比L-k%L小，自然就不比L小，因为后面的字符都是已经匹配上的，所以为了方便编写，程序里面就直接去看是否会比L小就可以了。
代码
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define pb push_back
#define bitnum(a) __builtin_popcount(a)
//返回a中有多少个1，注意是32为无符号整数
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 1e6+10;
int sa[N],cnt[N],pos[N],rk[N],oldrk[N],ht[N],n,m;
char str[N],s[2];
bool cmp(int a,int b,int k)
{
return oldrk[a]==oldrk[b]&&oldrk[a+k]==oldrk[b+k];
}
void getsa()
{
memset(cnt,0,sizeof(cnt));
m=122;
for(int i=1;i<=n;i++) ++cnt[rk[i]=str[i]];
for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
for(int i=n;i;i--) sa[cnt[rk[i]]--]=i;
for(int k=1;k<=n;k<<=1)
{
int num=0;
for(int i=n-k+1;i<=n;i++) pos[++num]=i;
for(int i=1;i<=n;i++) if(sa[i]>k) pos[++num]=sa[i]-k;
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++) ++cnt[rk[i]];
for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
for(int i=n;i;i--) sa[cnt[rk[pos[i]]]--]=pos[i];
num=0;
memcpy(oldrk,rk,sizeof(rk));
for(int i=1;i<=n;i++) rk[sa[i]]=cmp(sa[i],sa[i-1],k)?num:++num;
if(num==n) break;
m=num;
}
for(int i=1;i<=n;i++) rk[sa[i]]=i;
int k=0;
for(int i=1;i<=n;i++)
{
if(k) --k;
while(str[i+k]==str[sa[rk[i]-1]+k]) ++k;
ht[rk[i]]=k;
}
}
int dp[N][20];
void RMQ()
{
for(int i=1;i<=n;i++) dp[i][0]=ht[i];
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
int query(int l,int r)
{
int k=0;
while((1<<(k+1))<=(r-l+1)) ++k;
return min(dp[l][k],dp[r-(1<<k)+1][k]);
}
int lcp(int i,int j)
{
i=rk[i],j=rk[j];
if(i>j) swap(i,j);
return query(i+1,j);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s);
str[i]=s[0];
}
getsa();
RMQ();
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j+i<=n;j+=i)
{
int now=lcp(j,j+i);
int num=now/i+1;
int k=j-(i-now%i);
if(k>0&&lcp(k,k+i)>=i) num++;
ans=max(ans,num);
}
}
printf("%d
",ans);
}
return 0;
}