https://cn.vjudge.net/problem/POJ-3693

The repetition number of a string is defined as the maximum number R such that the string can be partitioned into R same consecutive substrings. For example, the repetition number of "ababab" is 3 and "ababa" is 1.

Given a string containing lowercase letters, you are to find a substring of it with maximum repetition number.

Input

The input consists of multiple test cases. Each test case contains exactly one line, which
gives a non-empty string consisting of lowercase letters. The length of the string will not be greater than 100,000.

The last test case is followed by a line containing a '#'.

Output

For each test case, print a line containing the test case number( beginning with 1) followed by the substring of maximum repetition number. If there are multiple substrings of maximum repetition number, print the lexicographically smallest one.

Sample Input

ccabababc
daabbccaa
#

Sample Output

Case 1: ababab
Case 2: aa

题意：求重复次数最多的连续重复子串，并且要求字典序最小的

思路：重复次数最多和前面那道题一样，关键就是字典序最小

存一下重复次数最多的长度，根据sa数组的性质，字典序小的在前面，外层从小到大枚举i，内层枚举l，第一个满足lcp(sa[i],sa[i]+l)>=(ans-1)*l，那么这个一定是字典序最小的

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath> 
#include<iostream>
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
/*
*suffix array
*倍增算法  O(n*logn)
*待排序数组长度为n,放在0~n-1中，在最后面补一个0
*build_sa( ,n+1, );//注意是n+1;
*getHeight(,n);
*例如：
*n   = 8;
*num[]   = { 1, 1, 2, 1, 1, 1, 1, 2, $ };注意num最后一位为0，其他大于0
*Rank[]  = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };Rank[0~n-1]为有效值，Rank[n]必定为0无效值
*sa[]    = { 8, 3, 4, 5, 0, 6, 1, 7, 2 };sa[1~n]为有效值，sa[0]必定为n是无效值
*height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]为有效值
*
*/
 
int sa[MAXN];//SA数组，表示将S的n个后缀从小到大排序后把排好序的
             //的后缀的开头位置顺次放入SA中
int t1[MAXN],t2[MAXN],c[MAXN];//求SA数组需要的中间变量，不需要赋值
int Rank[MAXN],height[MAXN];
//待排序的字符串放在s数组中，从s[0]到s[n-1],长度为n,且最大值小于m,
//除s[n-1]外的所有s[i]都大于0，r[n-1]=0
//函数结束以后结果放在sa数组中
void build_sa(int s[],int n,int m)
{
    int i,j,p,*x=t1,*y=t2;
    //第一轮基数排序，如果s的最大值很大，可改为快速排序
    for(i=0;i<m;i++)c[i]=0;
    for(i=0;i<n;i++)c[x[i]=s[i]]++;
    for(i=1;i<m;i++)c[i]+=c[i-1];
    for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
    for(j=1;j<=n;j<<=1)
    {
        p=0;
        //直接利用sa数组排序第二关键字
        for(i=n-j;i<n;i++)y[p++]=i;//后面的j个数第二关键字为空的最小
        for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
        //这样数组y保存的就是按照第二关键字排序的结果
        //基数排序第一关键字
        for(i=0;i<m;i++)c[i]=0;
        for(i=0;i<n;i++)c[x[y[i]]]++;
        for(i=1;i<m;i++)c[i]+=c[i-1];
        for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
        //根据sa和x数组计算新的x数组
        swap(x,y);
        p=1;x[sa[0]]=0;
        for(i=1;i<n;i++)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;
        if(p>=n)break;
        m=p;//下次基数排序的最大值
    }
}
void getHeight(int s[],int n)
{
    int i,j,k=0;
    for(i=0;i<=n;i++) Rank[sa[i]]=i;
    for(i=0;i<n;i++)
    {
        if(k)k--;
        j=sa[Rank[i]-1];
        while(s[i+k]==s[j+k])k++;
        height[Rank[i]]=k;
    }
}
 
char str[MAXN];
int s[MAXN];
int dp[MAXN][20];
void rmq_st_min(int n){
	for(int i=1;i<=n;i++) dp[i][0]=height[i];
	int m=log2(1.0*n);
	for(int j=1;j<=m;j++){
		int t=n-(1<<j)+1;
		for(int i=1;i<=t;i++){
			dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
		}
	}
}
int find_min(int l,int r){
	int k=log2(1.0*(r-l+1));
	return min(dp[l][k],dp[r-(1<<k)+1][k]);
}
int find(int a,int b){
	a=Rank[a];
	b=Rank[b];
	if(a>b) swap(a,b);
	return find_min(a+1,b);
}
int L[MAXN],tot=0;
int main()
{   
    int cas=0;
    while(~scanf("%s",str)){
    	if(str[0]=='#') break;
    	int len=strlen(str);
    	for(int i=0;i<=len;i++) s[i]=str[i];
    	build_sa(s,len+1,128);
    	getHeight(s,len);
    	rmq_st_min(len);
    	int ans=1;
    	tot=0;
    	for(int l=1;l<len;l++){
    		for(int i=0;i+l<len;i+=l){
    			int cnt=find(i,i+l);
    			int k=i-(l-cnt%l);
    			cnt=cnt/l+1;
    			if(k>=0&&find(k,k+l)>=l){
    				cnt++;
				}
    			if(cnt>ans){
    				tot=0;
    				L[tot++]=l;
    				ans=cnt;
				}
				else if(cnt==ans){
					L[tot++]=l;
				}
			}
		}
		int be=0,LEN=len;
		bool flag=false;
		for(int i=1;i<=len;i++){
			for(int j=0;j<tot;j++){
				if(find(sa[i],sa[i]+L[j])>=(ans-1)*L[j]){
					be=sa[i];
					LEN=L[j]*ans;
					flag=true;
					break;
				}
			}
			if(flag) break;
		}
    	printf("Case %d: ",++cas);
    	for(int i=0;i<LEN;i++) printf("%c",str[be+i]);
		printf("\n");
	}
    return 0;
}