spoj687 REPEATS - Repeats (后缀数组+rmq)

A string s is called an (k,l)-repeat if s is obtained by concatenating k>=1 times some seed string t with length l>=1. For example, the string

s = abaabaabaaba

is a (4,3)-repeat with t = aba as its seed string. That is, the seed string t is 3 characters long, and the whole string s is obtained by repeating t 4 times.

Write a program for the following task: Your program is given a long string u consisting of characters ‘a’ and/or ‘b’ as input. Your program must find some (k,l)-repeat that occurs as substring within u with k as large as possible. For example, the input string

u = babbabaabaabaabab

contains the underlined (4,3)-repeat s starting at position 5. Since u contains no other contiguous substring with more than 4 repeats, your program must output the maximum k.

Input

In the first line of the input contains H- the number of test cases (H <= 20). H test cases follow. First line of each test cases is n - length of the input string (n <= 50000), The next n lines contain the input string, one character (either ‘a’ or ‘b’) per
line, in order.

Output

For each test cases, you should write exactly one interger k in a line - the repeat count that is maximized.

Example

Input:

1

17

b

a

b

b

a

b

a

a

b

a

a

b

a

a

b

a

b

Output:

题意：给你一个长为n的字符串，然后让你找到重复次数最多的子串，并输出重复次数。

思路：这题想了很久，一开始看不懂罗穗蹇的思路(sigh),最后终于看懂了.我们先记重复的串的单位串为元串，先枚举重复的串的长度l(注意到重复次数为1一定是可以的，我们只要找到任意一个个字符就行，所以我们只要考虑重复次数大于等于2的情况)，如果重复次数等于2，所以我们找到的子串（由多个元串组成）一定经过a[0],a[l],a[2*l],...a[k*l](k*l<n)等倍数点的相邻两个，因为如果只经过一个倍数点，那么这个子串的最大长度为2*l-1，不可能由两个长度为l的元串组成。所以我们对于每一个枚举的长度l，找到所有相邻倍数节点a[i*l]和a[(i+1)*l]向前和向后匹配的字符串的长度(这里指两个要匹配的字符串分别以a[i*l],a[(i+1)*l]为首字符)，然后取最大值就行。这里向后匹配很简单，用后缀数组+rmq就行了，关键是向前匹配比较难处理。这里可以这样考虑，设a[i*l]和a[(i+1)*l]两个节点为首节点匹配的最大长度为k，如果k%l==0,那么就不用考虑向前匹配了，算出来的k/l+1就是循环次数，如果k%l!=0,那么就说明除了匹配k/l个循环节，还多出来k%l个字符串，那么如果i*l位置前l-k/l个字符为开头的后缀和(i+1)*l位置前l-k/l个字符为开头的后缀匹配的字符大于等于l-k/l,那么就说明还能多产生一个循环节，这里k/l+1要再加1.

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<set>

#include<string>

#include<bitset>

#include<algorithm>

using namespace std;

#define lson th<<1

#define rson th<<1|1

typedef long long ll;

typedef long double ldb;

#define inf 99999999

#define pi acos(-1.0)

#define maxn 50050

int sa[maxn],a[maxn];

int wa[maxn],wb[maxn],wv[maxn],we[maxn];

int rk[maxn],height[maxn];

int cmp(int *r,int a,int b,int l){

    return r[a]==r[b]&&r[a+l]==r[b+l];

}

void build_sa(int *r,int n,int m)

{

    int i,j,p,*x=wa,*y=wb,*t;

    for(i=0;i<m;i++)we[i]=0;

    for(i=0;i<n;i++)we[x[i]=r[i]]++;

    for(i=1;i<m;i++)we[i]+=we[i-1];

    for(i=n-1;i>=0;i--)sa[--we[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++)we[i]=0;

        for(i=0;i<n;i++)we[wv[i]]++;

        for(i=1;i<m;i++)we[i]+=we[i-1];

        for(i=n-1;i>=0;i--)sa[--we[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 n)

{

    int i,j,k=0;

    for(i=1;i<=n;i++)rk[sa[i]]=i;

    for(i=0;i<n;height[rk[i++] ]=k){

        for(k?k--:0,j=sa[rk[i]-1];r[i+k]==r[j+k];k++);

    }

}

int minx[maxn][30];

void init_rmq(int n)

{

    int i,j;

    height[1]=inf;

    for(i=1;i<=n;i++)minx[i][0]=height[i];

    for(j=1;j<=16;j++){

        for(i=1;i<=n;i++){

            if(i+(1<<j)-1<=n){

                minx[i][j]=min(minx[i][j-1],minx[i+(1<<(j-1))][j-1]);

            }

        }

    }

}

int lcp(int l,int r)

{

    int k,i;

    if(l>r)swap(l,r);

    l++;

    k=(log((r-l+1)*1.0)/log(2.0));

    return min(minx[l][k],minx[r-(1<<k)+1][k]);

}

int main()

{

    int n,m,i,j,T,l,beishu,yushu,len;

    scanf("%d",&T);

    char s[10];

    while(T--)

    {

        scanf("%d",&n);

        for(i=0;i<n;i++){

            scanf("%s",s);

            a[i]=s[0]-'a'+1;

        }

        a[n]=0;

        build_sa(a,n+1,130);

        calheight(a,n);

        init_rmq(n);

        int ans=1;

        for(l=1;l<=n;l++){

            for(i=0;i+l<n;i+=l){

                len=lcp(rk[i],rk[i+l] );

                beishu=len/l+1;

                yushu=len%l;

                if(i-(l-yushu)>=0 && yushu!=0 && lcp(rk[i-(l-yushu) ],rk[i+l-(l-yushu) ])>=yushu ){

                    beishu++;

                }

                ans=max(ans,beishu);

            }

        }

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

spoj687 REPEATS - Repeats (后缀数组+rmq)

Input

Output

Example

最新文章

热门文章