程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ3693:Maximum repetition substring(後綴數組+RMQ)

POJ3693:Maximum repetition substring(後綴數組+RMQ)

編輯：C++入門知識

POJ3693:Maximum repetition substring(後綴數組+RMQ)

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

Source

2008 Asia Hefei Regional Contest Online by USTC

題意:求重復次數最多的連續重復子串，並且要求字典序最小的
還是論文裡的題目
分析：

容易想到的就是枚舉長度為L，然後看長度為L的字符串最多連續出現幾次。

長度為L的串重復出現，那麼st[0],st[l],st[2*l]……st[k*l]中肯定有兩個連續的出現在字符串中。不然肯定長度不超過2*L啊。那麼我們就枚舉連續的兩個，然後從這兩個字符前後匹配，看最多能匹配多遠。

即以st[i*l],st[i*l+l]前後匹配，這裡是通過查詢suffix(i*l),suffix(i*l+l)的最長公共前綴

通過rank值能找到i*l,與i*l+l的排名，我們要查詢的是這段區間的height的最小值，通過RMQ預處理

達到查詢為0(1)的復雜度，設LCP長度為M, 則答案顯然為M / L + 1, 但這只是以i*l和i*l+l為起點的情況, 不過有一點是可以確定的。如果目標子串包含了

i*l和i*l+l。那麼 i*l一定是和i*l+l匹配的。因為目標串中p一定和p+l匹配。這樣才能滿足子串長度為l。先在要解決的就是起點不在這兩個位置上怎麼辦了。

得到M/L+1我們可以試著把答案變大。如果M%L!=0我們可以把長度補齊到L的整數倍。即在前面增加(L-M%L)的字符.看能不能使答案變大。為什麼這樣做是可以的呢？因為我們要使啊、答案變大往後擴展肯定不行了。因為後面已經不匹配了。但是我們為什麼擴展 (L-M%L)這麼多就行了呢。比這個小肯定是不行的。因為還是沒到L的整數倍。比這個多能行的話。去這個值一定能行。因為p是和p+L匹配的。既然取得比這個多。大不了往右平移幾個還是能使 M%L得到匹配。那為什麼只擴展一個長度L。不擴展多個呢。因為你是枚舉每個i*l和i*l+l。你擴展2個或兩個以上就是前面的 i*l和i*l+l的情況了。這一步完成後我們只能得到度數最大長度可能的取值。剩下的工作就是找字典序最小了。通過sa數組進行枚舉，取到的第一組，肯定是字典序最小的。

#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define LS 2*i
#define RS 2*i+1
#define UP(i,x,y) for(i=x;i<=y;i++)
#define DOWN(i,x,y) for(i=x;i>=y;i--)
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define LL long long
#define N 1000005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EXP 1e-8
int wa[N],wb[N],wsf[N],wv[N],sa[N];
int rank[N],height[N],s[N],a[N];
char str[N],str1[N],str2[N];
//sa:字典序中排第i位的起始位置在str中第sa[i]
//rank:就是str第i個位置的後綴是在字典序排第幾
//height：字典序排i和i-1的後綴的最長公共前綴
int cmp(int *r,int a,int b,int k)
{
    return r[a]==r[b]&&r[a+k]==r[b+k];
}
void getsa(int *r,int *sa,int n,int m)//n要包含末尾添加的0
{
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0; i=0; i--)  sa[--wsf[x[i]]]=i;
    p=1;
    j=1;
    for(; p=j)  y[p++]=sa[i]-j;
        for(i=0; i=0; i--)  sa[--wsf[wv[i]]]=y[i];
        t=x;
        x=y;
        y=t;
        x[sa[0]]=0;
        for(p=1,i=1; i>1)]);
        }
    }
}
int lcp(int a,int b) {//詢問a,b後綴的最長公共前綴
    a = rank[a];    b = rank[b];
    if(a > b) swap(a,b);
    a ++;
    int t = Log[b - a + 1];
    return min(best[t][a] , best[t][b - (1<=0 && k%l)
                {
                    if(lcp(t,t+l)>=k) m++;
                }
                if(m>maxn)
                {
                    len = 0;
                    ans[len++] = l;
                    maxn = m;
                }
                else if(m == maxn)
                {
                    ans[len++] = l;
                }
            }
        }
        int start,flag = 0;
        UP(i,1,n)
        {
            if(flag)
            break;
            UP(j,0,len-1)
            {
                int tem = ans[j];
                if(lcp(sa[i],sa[i]+tem)>=(maxn-1)*tem)
                {
                    start = sa[i];
                    l = tem*maxn;
                    flag = 1;
                    break;
                }
            }
        }
        printf("Case %d: ",cas++);
        UP(i,0,l-1)
        printf("%c",str[start+i]);
        printf("\n");
    }
}