poj 3261 Milk Patterns

題目思路：後綴數組，求可重疊的重復k次子串。

[cpp] 
#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#include<string> 
#include<queue> 
#include<algorithm> 
#include<vector> 
#include<stack> 
#include<list> 
//#include<iostream> 
#include<map> 
using namespace std; 
#define inf 0x3f3f3f3f 
#define M 1100000 
int max(int a,int b) 
{ 
    return a>b?a:b; 
} 
int min(int a,int b) 
{ 
    return a<b?a:b; 
} 
struct node 
{ 
    int v,id; 
    bool operator<(const node a)const 
    { 
        return v<a.v; 
    } 
}a[M]; 
int r[M],rank[M],sa[M],height[M]; 
int ws[M],wv[M],wa[M],wb[M]; 
bool cmp(int *r,int a,int b,int l) 
{ 
    return r[a]==r[b]&&r[a+l]==r[b+l]; 
} 
void da(int n,int m) 
{ 
    int i,j,p; 
    int *x=wa,*y=wb; 
    for(i=0;i<n;i++) 
    { 
        a[i].v=r[i]; 
        a[i].id=i; 
    } 
    sort(a,a+n); 
    p=1; 
    x[a[0].id]=0; 
    for(i=1;i<n;i++) 
    { 
        if(a[i].v==a[i-1].v) x[a[i].id]=p-1; 
        else x[a[i].id]=p++; 
    } 
     m=p; 
    for(i=0;i<m;i++) ws[i]=0; 
    for(i=0;i<n;i++) ws[x[i]]++; 
    for(i=1;i<m;i++) ws[i]+=ws[i-1]; 
    for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i; 
    for(j=1,p=1;p<n;j*=2,m=p) 
    { 
        p=0; 
        for(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++) 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]; 
        p=1; 
        swap(x,y); 
        x[sa[0]]=0; 
        for(i=1;i<n;i++) 
        { 
            if(cmp(y,sa[i],sa[i-1],j)) x[sa[i]]=p-1; 
            else x[sa[i]]=p++; 
        } 
 
    } 
} 
void calheight(int n) 
{ 
    int i,j,k; 
    for(i=1;i<=n;i++) rank[sa[i]]=i; 
    k=0; 
    for(i=0;i<n;i++) 
    { 
        int tmp=sa[rank[i]-1]; 
        for(j=k;r[i+k]==r[tmp+k];k++); 
        height[rank[i]]=k; 
        k?--k:0; 
    } 
} 
int check(int n,int len,int k) 
{ 
    int num=0,i; 
    for(i=2;i<=n;i++) 
    { 
        if(height[i]<len) 
            num=0; 
        else 
        { 
            num++; 
            if(num>=k-1) return 1; 
        } 
    } 
    return 0; 
} 
int main() 
{ 
    int i,n,k,left,right,mid; 
    while(scanf("%d%d",&n,&k)!=EOF) 
    { 
        for(i=0;i<n;i++) scanf("%d",&r[i]); 
        r[n]=0; 
        da(n+1,1000100); 
        calheight(n); 
        left=2;right=n; 
        while(left<=right) 
        { 
            mid=(left+right)>>1; 
            if(check(n,mid,k)) left=mid+1; 
            else right=mid-1; 
        } 
        printf("%d\n",right); 
    } 
}