博主链接

题目链接

题意:

对于给出的字符串(长度<= 50000,只包含字符’a’或’b’)找到最大的k使得存在某个字符串t重复k次是给出的字符串的子串

题解:

如果每一个循环节的长度为len, 那么在原字符串S中, S[i*len]与S[(i + 1)len]一定会被包含在答案的子串当中那么枚举可能的答案的循环节的长度, 然后枚举可能的位置, 对于每一组可能被包含的位置S[ilen], S[(i + 1)len]求出其对应后缀的最长公共前缀长度L, 则该循环节至少循环了L/len + 1次, 但是当L%len != 0时, 后面多余出来的部分(长度L%len的部分)可能和前面的拼凑成循环节, 于是对于位置ilen - (len - L % len)和(i + 1)*len - (len - L % len)求其后缀的最长公共前缀长度, 如果大于之前的结果,自然就说明从这个位置开始可以比之前多一个循环节, 于是这样枚举得到最多循环次数

代码:

#include<stdio.h>
#include<string.h>
#include<map>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
#define REP(i,n) for(i=0;i<(n);++i)
#define UPTO(i,l,h) for(i=(l);i<=(h);++i)
#define DOWN(i,h,l) for(i=(h);i>=(l);--i)
const int maxn=1e6+10;
const int mod=1e9+7;
typedef long long ll;
template <typename T, int LEN>
struct suffixarray{
    //rank[i] 第i个后缀的排名; SA[i] 排名为i的后缀位置; Height[i] 排名为i的后缀与排名为(i-1)的后缀的LCP
	int str[LEN*3],sa[LEN*3];
	int rank[LEN],height[LEN];
	int id[LEN];
	int best[LEN][20];
	int len;
	bool equal(int *str, int a, int b){
		return str[a]==str[b]&&str[a+1]==str[b+1]&&str[a+2]==str[b+2];
	}
	bool cmp3(int *str, int *nstr, int a, int b){
		if(str[a]!=str[b])return str[a]<str[b];
		if(str[a+1]!=str[b+1])return str[a+1]<str[b+1];
		return nstr[a+b%3]<nstr[b+b%3];
	}
	void radixsort(int *str, int *sa, int *res, int n, int m){
		int i;
		REP(i,m)id[i]=0;
		REP(i,n)++id[str[sa[i]]];
		REP(i,m)id[i+1]+=id[i];
		DOWN(i,n-1,0)res[--id[str[sa[i]]]]=sa[i];
	}
	void dc3(int *str, int *sa, int n, int m){
		#define F(x) ((x)/3+((x)%3==1?0:one))
		#define G(x) ((x)<one?(x)*3+1:((x)-one)*3+2)
		int *nstr=str+n, *nsa=sa+n, *tmpa=rank, *tmpb=height;
		int i,j,k,len=0,num=0,zero=0,one=(n+1)/3;
		REP(i,n)if(i%3)tmpa[len++]=i;
		str[n]=str[n+1]=0;
		radixsort(str+2, tmpa, tmpb, len, m);
		radixsort(str+1, tmpb, tmpa, len, m);
		radixsort(str+0, tmpa, tmpb, len, m);
		nstr[F(tmpb[0])]=num++;
		UPTO(i,1,len-1)
			nstr[F(tmpb[i])]=equal(str,tmpb[i-1],tmpb[i])?num-1:num++;
		if(num<len)dc3(nstr,nsa,len,num);
		else REP(i,len)nsa[nstr[i]]=i;
		if(n%3==1)tmpa[zero++]=n-1;
		REP(i,len)if(nsa[i]<one)tmpa[zero++]=nsa[i]*3;
		radixsort(str, tmpa, tmpb, zero, m);
		REP(i,len)tmpa[nsa[i]=G(nsa[i])]=i;
		i=j=0;
		REP(k,n)
		if(j>=len||(i<zero&&cmp3(str,tmpa,tmpb[i],nsa[j])))sa[k]=tmpb[i++];
		else sa[k]=nsa[j++];
	}
	void initSA(T *s, int n,int m){
		int i,j,k=0;
		str[len=n]=0;//末尾增加一个0,这样就省去一些特殊情况的讨论,也就是最后一个mod 3刚好等于0
		REP(i,n)str[i]=s[i];
		dc3(str,sa,n+1,m);      //可以切换成dc3
		REP(i,n)sa[i]=sa[i+1];//第0小的默认为最后一个字符0,所以答案向前移动一位,da算法不用
        //da(str,sa,n,m);
		REP(i,n)rank[sa[i]]=i;
		REP(i,n)//计算height数组
		{
			if(k)--k;
			if(rank[i])for(j=sa[rank[i]-1];str[i+k]==str[j+k];++k);
			else k=0;
			height[rank[i]]=k;
		}
	}
	void initRMQ(){
		int i,j;
		int m=(int)(log(len*1.0)/log(2.0));
		REP(i,len)best[i][0]=height[i];
		for(j=1;j<=m;++j)
			for(i=0;i+(1<<j)-1<len;++i)
				best[i][j]=min(best[i][j-1],best[i+(1<<(j-1))][j-1]);
	}
	int RMQ(int l, int r){
		int k=int(log(r-l+1.0)/log(2.0));
		return min(best[l][k],best[r-(1<<k)+1][k]);
	}
	int LCPSA(int a, int b){//查询区间RMQ(i,j)
		a=rank[a],b=rank[b];
		if(a>b)swap(a,b);
		return RMQ(a+1,b);
	}
};
suffixarray<int,maxn> msa;
map<int ,int > mymap;   //计算m,m表示不同字符个数,如果是字母直接用256
char s[maxn];
int ss[maxn];
int main(){
    int t,Max=0,ans,k;
    scanf("%d",&t);
    while(t--){
        int len;
        Max=1;
        scanf("%d",&len);
        for(int i=0;i<len;i++){
            scanf("%s",s);
            ss[i]=s[0]-'a'+1;
        }
        msa.initSA(ss,len,4);
        msa.initRMQ();
        for(int i=1;i<=len;i++){  //枚举长度
            for(int j=0;j+i<len;j+=i){  //+i极大的降低了复杂度
                //但也产生了需要向前比较的问题
                ans=msa.LCPSA(j,j+i); //公共后缀的长度
                k=j-(i-ans%i); //前推到k位置
                ans=ans/i+1;  //出现次数
                if(k>=0&&msa.LCPSA(k,k+i)>=i)ans++;
                //printf("L=%d,R=%d\n",i,ans);
                Max=max(Max,ans);
            }
        }
        printf("%d\n",Max);
    }
	return 0;
}