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.
Link : Problem
Solution :
O(n^2) Solution:
-
Use KMP for each suffix.Then determine the maximum repeatating for each. Output the maximum. But to find the leaxographically smallest , We need to do some other works.
Pseudocode:
iM = 0;
for each suffix starting from i to strlen(s)
temp= Maximum Repeatation in this suffix
iM= max(iM , temp) ;
N log N Solution :
First Build the suffix array and LCP array.
Every Repating String is in form S = A^k , A is concatanated k times to form this string.
Let, len be possible length of A such that A can form a substring of S by concatanating 1 or moretime.for each length We do the following.
Only keep the values That produces maximum k
To find the lexicographic minimal string, We iterate in the order of the suffix array and check whether it generates a Repeating string with maximum k. If it is then Store the position and break
output the substring
Here is my code:
/*
*************************
Id : Matrix.code
Task: HDU 2459
Date: 2016-01-30
**************************
*/
#include <bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/*------- Constants---- */
#define Long long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define SZ(a) (int) a.size()
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define Si(n) si(n)
#define Sii(a,b) si(a);si(b)
#define Siii(a,b,c) si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
/*************************** END OF TEMPLATE ****************************/
const int N = 1e5+5;
int wa[N],wb[N],wv[N],wc[N];
int r[N],sa[N],rak[N], height[N];
// compare of two suffix starting at a & b and gap = l
int cmp(int *r,int a,int b,int l)
{
return r[a] == r[b] && r[a+l] == r[b+l];
}
void da(int *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for( i=0;i<m;i++) wc[i]=0;
for( i=0;i<n;i++) wc[x[i]=r[i]] ++;
for( i=1;i<m;i++) wc[i] += wc[i-1];
for( i= n-1;i>=0;i--)sa[--wc[x[i]]] = i;
for( j= 1,p=1;p<n;j*=2,m=p){
for(p=0,i=n-j;i<n;i++)y[p++] = i;
for(i=0;i<n;i++)if(sa[i] >= j) y[p++] = sa[i] - j;
for(i=0;i<n;i++)wv[i] = x[y[i]];
for(i=0;i<m;i++) wc[i] = 0;
for(i=0;i<n;i++) wc[wv[i]] ++;
for(i=1;i<m;i++) wc[i] += wc[i-1];
for(i=n-1;i>=0;i--) sa[--wc[wv[i]]] = y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]] = 0,i=1;i<n;i++) x[sa[i]]= cmp(y,sa[i-1],sa[i],j) ? p-1:p++;
}
}
void calheight(int *r,int *sa,int n)
{
int i,j,k=0;
for(i=1;i<=n;i++) rak[sa[i]] = i;
for(i=0;i<n;height[rak[i++]] = k ) {
for(k?k--:0, j=sa[rak[i]-1] ; r[i+k] == r[j+k] ; k ++) ;
}
}
int dp[N][20];
void initRMQ(int n)
{
for(int i= 1; i <= n; i ++) dp[i][0] = height[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 askRMQ(int L,int R)
{
if(L>R)swap(L,R);
L ++;
int k = 0;
while((1<<(k+1)) <= R-L+1) k++;
return min(dp[L][k], dp[R - (1<<k) + 1][k]);
}
char str[N];
int main()
{
//freopen("in.txt","r",stdin);
int cs= 0;
while(scanf("%s",str)) {
if(str[0]=='#') break;
int p = strlen(str);
for(int i= 0; str[i]; i ++ ) {
r[i] = str[i] - 'a' + 1;
}
r[p] = 0;
da(r,sa,p+1,32);
calheight(r,sa,p);
initRMQ(p);
int n = p;
vector<int> v;
int iM = 1;
/*
for(int i = 0; i <= p; i ++) printf("%d ", sa[i]);puts("");
for(int i = 0; i <= p; i ++) printf("%d ",height[i]);puts("");
for(int i = 0;i <= p; i ++) printf("%d ",rak[i]);*/
for(int len = 1;len <= n; len ++ ) {
for(int i = 0; i + len < n ; i += len ) {
int k = askRMQ(rak[i], rak[i+len] );
int step = k / len + 1;
int fix = i - (len - k % len) ;
if(fix >= 0 && k % len ) {
int noo = askRMQ(rak[fix], rak[fix + len] ) ;
step = max(step, noo / len + 1);
}
if(step > iM ){
v.clear();
v.pb(len);
iM=step;
}else if(step== iM) {
v.pb(len);
}
}
}
v.push_back(1);
sort(all(v));
v.resize(unique(all(v)) - v.begin());
int pos = 0;
int Len = -1;
for(int i= 1; i <= n && Len == -1 ; i ++ ) {
for(int j= 0; j < v.size(); j ++ ) {
int len = v[j];
int ans = askRMQ(i, rak[sa[i] + len]) ;
if(ans >= (iM - 1) * len) {
pos = sa[i];
Len = iM * len;
break;
}
}
}
printf("Case %d: ",++cs);
for(int i = 0; i < Len; i ++ ) printf("%c" , str[pos +i ]);
printf("\n");
}
return 0;
}
Code for Fun 