POJ 3693 Maximum repetition substring(后缀数组[重复次数最多的连续重复子串])
2016-11-05       个评论    来源：queuelovestack的专栏
我要投稿

# POJ 3693 Maximum repetition substring

Accept: 0 Submit: 0
Time Limit: 1000 MS Memory Limit : 65536 K

## Problem Description

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, whichgives 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.

ccabababc
daabbccaa
#

Case 1: ababab
Case 2: aa

## Problem Idea

【题意】

【类型】

【分析】

"重复次数最多的连续重复子串"解法(摘自罗穗骞的国家集训队论文):

ps：基本思路在罗穗骞的论文里已经说得比较清楚了，而我在这里要提的是论文里比较模糊的部分

“S肯定包括了字符r[0], r[L], r[L*2],r[L*3], ……中的某相邻的两个”

“只须看字符r[L*i]和r[L*(i+1)]往前和往后各能匹配到多远”，对于往后能匹配到多远，这个直接根据最长公共前缀就能很容易得到，即上图中的后缀Suffix(6)和后缀Suffix(9)的最长公共前缀。而对于往前能匹配到多远，我们当然可以一开始就把字符串反过来拼在后面，这样也能根据最长公共前缀来看往前能匹配到多远，但这样效率就比较低了。

【时间复杂度&&优化】
O(nlogn)

## Source Code

```/*Sherlock and Watson and Adler*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 5005;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
const int MAXN = 100005;
//rnk从0开始
//sa从1开始,因为最后一个字符(最小的)排在第0位
//height从1开始,因为表示的是sa[i - 1]和sa[i]
//倍增算法 O(nlogn)
int wa[MAXN], wb[MAXN], wv[MAXN], ws_[MAXN];
//Suffix函数的参数m代表字符串中字符的取值范围,是基数排序的一个参数,如果原序列都是字母可以直接取128,如果原序列本身都是整数的话,则m可以取比最大的整数大1的值
//待排序的字符串放在r数组中,从r[0]到r[n-1]，长度为n
//为了方便比较大小,可以在字符串后面添加一个字符,这个字符没有在前面的字符中出现过,而且比前面的字符都要小
//同上,为了函数操作的方便,约定除r[n-1]外所有的r[i]都大于0,r[n-1]=0
//函数结束后,结果放在sa数组中,从sa[0]到sa[n-1]
void Suffix(int *r, int *sa, int n, int m)
{
int i, j, k, *x = wa, *y = wb, *t;
//对长度为1的字符串排序
//一般来说,在字符串的题目中,r的最大值不会很大,所以这里使用了基数排序
//如果r的最大值很大,那么把这段代码改成快速排序
for(i = 0; i < m; ++i) ws_[i] = 0;
for(i = 0; i < n; ++i) ws_[x[i] = r[i]]++;//统计字符的个数
for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];//统计不大于字符i的字符个数
for(i = n - 1; i >= 0; --i) sa[--ws_[x[i]]] = i;//计算字符排名
//基数排序
//x数组保存的值相当于是rank值
for(j = 1, k = 1; k < n; j *= 2, m = k)
{
//j是当前字符串的长度,数组y保存的是对第二关键字排序的结果
//第二关键字排序
for(k = 0, i = n - j; i < n; ++i) y[k++] = i;//第二关键字为0的排在前面
for(i = 0; i < n; ++i) if(sa[i] >= j) y[k++] = sa[i] - j;//长度为j的子串sa[i]应该是长度为2 * j的子串sa[i] - j的后缀（第二关键字）,对所有的长度为2 * j的子串根据第二关键字来排序
for(i = 0; i < n; ++i) wv[i] = x[y[i]];//提取第一关键字
//按第一关键字排序 (原理同对长度为1的字符串排序)
for(i = 0; i < m; ++i) ws_[i] = 0;
for(i = 0; i < n; ++i) ws_[wv[i]]++;
for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
for(i = n - 1; i >= 0; --i) sa[--ws_[wv[i]]] = y[i];//按第一关键字,计算出了长度为2 * j的子串排名情况
//此时数组x是长度为j的子串的排名情况,数组y仍是根据第二关键字排序后的结果
//计算长度为2 * j的子串的排名情况,保存到数组x
t = x;
x = y;
y = t;
for(x[sa[0]] = 0, i = k = 1; i < n; ++i)
x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k - 1 : k++;
//若长度为2 * j的子串sa[i]与sa[i - 1]完全相同,则他们有相同的排名
}
}
int Rank[MAXN], height[MAXN], sa[MAXN], r[MAXN];
void calheight(int *r,int *sa,int n)
{
int i,j,k=0;
for(i=1; i<=n; i++)Rank[sa[i]]=i;
for(i=0; ib)
swap(a,b);
}
char s[MAXN];
int q[MAXN];
int main()
{
int i,j,k,ans,Max,cnt,p=1;
bool flag;
while(scanf("%s",s)&&s[0]!='#')
{
n=strlen(s);
Max=0;
for(i=0;s[i]!='\0';i++)
r[i]=s[i]-'a'+1;
r[i]=0;
Suffix(r,sa,n+1,27);
calheight(r,sa,n);
RMQ();
for(i=1;i<=n;i++)
{
for(j=0;j+i=0&&calprefix(k,k+i)>=i)
ans++;
//printf("L=%d,R=%d\n",i,ans);
if(Max=q[j]*(Max-1))
{
s[sa[i]+q[j]*Max]='\0';
flag=true;
printf("Case %d: %s\n",p++,s+sa[i]);
}
}
return 0;
}```