POJ 3261 Milk Patterns（後綴數組+二分答案+離散化）

題意：給定一個字符串，求至少出現k 次的最長重復子串，這k 個子串可以重疊。

分析：經典的後綴數組求解題：先二分答案，然後將後綴分成若干組。這裡要判斷的是有沒有一個組的符合要求的後綴個數（height[i] >= mid）不小於k。如果有，那麼存在
k 個相同的子串滿足條件，否則不存在

#include <cstdio>   
#include <iostream>   
#include <cstring>   
#include <algorithm>   
using namespace std;  
#define N 22222   
#define M 1111111   
#define INF 0x7FFFFFFF   
/****後綴數組模版****/  
#define F(x)((x)/3+((x)%3==1?0:tb)) //F(x)求出原字符串的suffix(x)在新的字符串中的起始位置   
#define G(x)((x)<tb?(x)*3+1:((x)-tb)*3+2) //G(x)是計算新字符串的suffix(x)在原字符串中的位置，和F(x)為互逆運算   
int wa[N],wb[N],wv[N],WS[M];  
int sa[N*3] ; //第i小的後綴，起始位置在源字符串的位置   
int rank1[N],height[N]; //rank 以i為起始位置的後綴在後綴排列中的名次   
int r[N*3]; //如果輸入是字符串，承接字符串，用來計算   
  
  
int c0(int *r,int a,int b) {  
    return r[a]==r[b] && r[a+1]==r[b+1] && r[a+2]==r[b+2];  
}  
int c12(int k,int *r,int a,int b) {  
    if(k==2)  
        return r[a]<r[b] || ( r[a]==r[b] && c12(1,r,a+1,b+1) );  
    else  
        return r[a]<r[b] || ( r[a]==r[b] && wv[a+1]<wv[b+1] );  
}  
void sort(int *r,int *a,int *b,int n,int m) {  
    int i;  
    for(i=0; i<n; i++)  
        wv[i]=r[a[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--)  
        b[--WS[wv[i]]]=a[i];  
    return;  
}  
  
//注意點：為了方便下面的遞歸處理，r數組和sa數組的大小都要是3*n   
void dc3(int *r,int *sa,int n,int m) { //rn數組保存的是遞歸處理的新字符串，san數組是新字符串的sa   
    int i , j , *rn = r+n , *san = sa+n , ta = 0 ,tb = (n+1)/3 , tbc = 0 , p;  
    r[n] = r[n+1] = 0;  
    for(i=0; i<n; i++) {  
        if(i%3!=0)  
            wa[tbc++]=i; //tbc表示起始位置模3為1或2的後綴個數   
    }  
    sort(r+2,wa,wb,tbc,m);  
    sort(r+1,wb,wa,tbc,m);  
    sort(r,wa,wb,tbc,m);  
    for(p=1,rn[F(wb[0])]=0,i=1; i<tbc; i++)  
        rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;  
    if(p<tbc)  
        dc3(rn,san,tbc,p);  
    else {  
        for(i=0; i<tbc; i++)  
            san[rn[i]]=i;  
    }  
//對所有起始位置模3等於0的後綴排序   
    for(i=0; i<tbc; i++) {  
        if(san[i]<tb)  
            wb[ta++]=san[i]*3;  
    }  
    if(n%3==1)  //n%3==1，要特殊處理suffix(n-1)   
        wb[ta++]=n-1;  
    sort(r,wb,wa,ta,m);  
    for(i=0; i<tbc; i++)  
        wv[wb[i] = G(san[i])]=i;  
//合並所有後綴的排序結果，保存在sa數組中   
    for(i=0,j=0,p=0; i<ta&&j<tbc; p++)  
        sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];  
    for(; i<ta; p++)  
        sa[p]=wa[i++];  
    for(; j<tbc; p++)  
        sa[p]=wb[j++];  
    return;  
}  
  
//height[i]=suffix(sa[i-1])和suffix(sa[i])的最長公共前綴，也就是排名相鄰的兩個後綴的最長公共前綴   
void calheight(int *r,int *sa,int n) {  
    int i,j,k=0;  
    for(i=1; i<=n; i++)  
        rank1[sa[i]]=i;  
    for(i=0; i<n; height[rank1[i++]]=k)  
        for(k?k--:0,j=sa[rank1[i]-1]; r[i+k]==r[j+k]; k++);  
}  
  
bool judge(int mid,int n,int k) {  
    int cnt = 1;  
    for(int i=1; i<=n; i++) {  
        if(height[i] >= mid) {  
            cnt ++;  
        } else cnt = 1;  
        if(cnt >= k) return true;  
    }  
    return false;  
}  
  
int main() {  
    int n,k;  
    cin >> n >> k;  
    for(int i=0; i<n; i++) {  
        scanf("%d",&r[i]);  
        r[i] ++;  
    }  
    r[n] = 0; //要保證結尾最小   
    dc3(r,sa,n+1,1000010);  
    calheight(r,sa,n);  
    int l=1, r=n,mid; //枚舉長度   
    int ans = 0;  
    while(l <= r) {  
        mid = (l+r) >> 1;  
        if(judge(mid,n,k)) {  
            ans = mid;  
            l = mid + 1;  
        } else {  
            r = mid - 1;  
        }  
    }  
    cout << ans << endl;  
    return 0;  
}  

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 22222
#define M 1111111
#define INF 0x7FFFFFFF
/****後綴數組模版****/
#define F(x)((x)/3+((x)%3==1?0:tb)) //F(x)求出原字符串的suffix(x)在新的字符串中的起始位置
#define G(x)((x)<tb?(x)*3+1:((x)-tb)*3+2) //G(x)是計算新字符串的suffix(x)在原字符串中的位置，和F(x)為互逆運算
int wa[N],wb[N],wv[N],WS[M];
int sa[N*3] ; //第i小的後綴，起始位置在源字符串的位置
int rank1[N],height[N]; //rank 以i為起始位置的後綴在後綴排列中的名次
int r[N*3]; //如果輸入是字符串，承接字符串，用來計算


int c0(int *r,int a,int b) {
    return r[a]==r[b] && r[a+1]==r[b+1] && r[a+2]==r[b+2];
}
int c12(int k,int *r,int a,int b) {
    if(k==2)
        return r[a]<r[b] || ( r[a]==r[b] && c12(1,r,a+1,b+1) );
    else
        return r[a]<r[b] || ( r[a]==r[b] && wv[a+1]<wv[b+1] );
}
void sort(int *r,int *a,int *b,int n,int m) {
    int i;
    for(i=0; i<n; i++)
        wv[i]=r[a[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--)
        b[--WS[wv[i]]]=a[i];
    return;
}

//注意點：為了方便下面的遞歸處理，r數組和sa數組的大小都要是3*n
void dc3(int *r,int *sa,int n,int m) { //rn數組保存的是遞歸處理的新字符串，san數組是新字符串的sa
    int i , j , *rn = r+n , *san = sa+n , ta = 0 ,tb = (n+1)/3 , tbc = 0 , p;
    r[n] = r[n+1] = 0;
    for(i=0; i<n; i++) {
        if(i%3!=0)
            wa[tbc++]=i; //tbc表示起始位置模3為1或2的後綴個數
    }
    sort(r+2,wa,wb,tbc,m);
    sort(r+1,wb,wa,tbc,m);
    sort(r,wa,wb,tbc,m);
    for(p=1,rn[F(wb[0])]=0,i=1; i<tbc; i++)
        rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
    if(p<tbc)
        dc3(rn,san,tbc,p);
    else {
        for(i=0; i<tbc; i++)
            san[rn[i]]=i;
    }
//對所有起始位置模3等於0的後綴排序
    for(i=0; i<tbc; i++) {
        if(san[i]<tb)
            wb[ta++]=san[i]*3;
    }
    if(n%3==1)  //n%3==1，要特殊處理suffix(n-1)
        wb[ta++]=n-1;
    sort(r,wb,wa,ta,m);
    for(i=0; i<tbc; i++)
        wv[wb[i] = G(san[i])]=i;
//合並所有後綴的排序結果，保存在sa數組中
    for(i=0,j=0,p=0; i<ta&&j<tbc; p++)
        sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
    for(; i<ta; p++)
        sa[p]=wa[i++];
    for(; j<tbc; p++)
        sa[p]=wb[j++];
    return;
}

//height[i]=suffix(sa[i-1])和suffix(sa[i])的最長公共前綴，也就是排名相鄰的兩個後綴的最長公共前綴
void calheight(int *r,int *sa,int n) {
    int i,j,k=0;
    for(i=1; i<=n; i++)
        rank1[sa[i]]=i;
    for(i=0; i<n; height[rank1[i++]]=k)
        for(k?k--:0,j=sa[rank1[i]-1]; r[i+k]==r[j+k]; k++);
}

bool judge(int mid,int n,int k) {
    int cnt = 1;
    for(int i=1; i<=n; i++) {
        if(height[i] >= mid) {
            cnt ++;
        } else cnt = 1;
        if(cnt >= k) return true;
    }
    return false;
}

int main() {
    int n,k;
    cin >> n >> k;
    for(int i=0; i<n; i++) {
        scanf("%d",&r[i]);
        r[i] ++;
    }
    r[n] = 0; //要保證結尾最小
    dc3(r,sa,n+1,1000010);
    calheight(r,sa,n);
    int l=1, r=n,mid; //枚舉長度
    int ans = 0;
    while(l <= r) {
        mid = (l+r) >> 1;
        if(judge(mid,n,k)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

因為m太大，而n只有2w，簡單的離散化之後，基數排序效率提高，總效率也提高了

#include <cstdio>   
#include <iostream>   
#include <cstring>   
#include <algorithm>   
using namespace std;  
#define N 22222   
#define INF 0x7FFFFFFF   
/****後綴數組模版****/  
#define F(x)((x)/3+((x)%3==1?0:tb)) //F(x)求出原字符串的suffix(x)在新的字符串中的起始位置   
#define G(x)((x)<tb?(x)*3+1:((x)-tb)*3+2) //G(x)是計算新字符串的suffix(x)在原字符串中的位置，和F(x)為互逆運算   
int wa[N],wb[N],wv[N],WS[N];  
int sa[N*3] ; //第i小的後綴，起始位置在源字符串的位置   
int rank1[N],height[N]; //rank 以i為起始位置的後綴在後綴排列中的名次   
int r[N*3]; //如果輸入是字符串，承接字符串，用來計算   
  
  
int c0(int *r,int a,int b) {  
    return r[a]==r[b] && r[a+1]==r[b+1] && r[a+2]==r[b+2];  
}  
int c12(int k,int *r,int a,int b) {  
    if(k==2)  
        return r[a]<r[b] || ( r[a]==r[b] && c12(1,r,a+1,b+1) );  
    else  
        return r[a]<r[b] || ( r[a]==r[b] && wv[a+1]<wv[b+1] );  
}  
void sort(int *r,int *a,int *b,int n,int m) {  
    int i;  
    for(i=0; i<n; i++)  
        wv[i]=r[a[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--)  
        b[--WS[wv[i]]]=a[i];  
    return;  
}  
  
//注意點：為了方便下面的遞歸處理，r數組和sa數組的大小都要是3*n   
void dc3(int *r,int *sa,int n,int m) { //rn數組保存的是遞歸處理的新字符串，san數組是新字符串的sa   
    int i , j , *rn = r+n , *san = sa+n , ta = 0 ,tb = (n+1)/3 , tbc = 0 , p;  
    r[n] = r[n+1] = 0;  
    for(i=0; i<n; i++) {  
        if(i%3!=0)  
            wa[tbc++]=i; //tbc表示起始位置模3為1或2的後綴個數   
    }  
    sort(r+2,wa,wb,tbc,m);  
    sort(r+1,wb,wa,tbc,m);  
    sort(r,wa,wb,tbc,m);  
    for(p=1,rn[F(wb[0])]=0,i=1; i<tbc; i++)  
        rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;  
    if(p<tbc)  
        dc3(rn,san,tbc,p);  
    else {  
        for(i=0; i<tbc; i++)  
            san[rn[i]]=i;  
    }  
//對所有起始位置模3等於0的後綴排序   
    for(i=0; i<tbc; i++) {  
        if(san[i]<tb)  
            wb[ta++]=san[i]*3;  
    }  
    if(n%3==1)  //n%3==1，要特殊處理suffix(n-1)   
        wb[ta++]=n-1;  
    sort(r,wb,wa,ta,m);  
    for(i=0; i<tbc; i++)  
        wv[wb[i] = G(san[i])]=i;  
//合並所有後綴的排序結果，保存在sa數組中   
    for(i=0,j=0,p=0; i<ta&&j<tbc; p++)  
        sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];  
    for(; i<ta; p++)  
        sa[p]=wa[i++];  
    for(; j<tbc; p++)  
        sa[p]=wb[j++];  
    return;  
}  
  
//height[i]=suffix(sa[i-1])和suffix(sa[i])的最長公共前綴，也就是排名相鄰的兩個後綴的最長公共前綴   
void calheight(int *r,int *sa,int n) {  
    int i,j,k=0;  
    for(i=1; i<=n; i++)  
        rank1[sa[i]]=i;  
    for(i=0; i<n; height[rank1[i++]]=k)  
        for(k?k--:0,j=sa[rank1[i]-1]; r[i+k]==r[j+k]; k++);  
}  
  
bool judge(int mid,int n,int k) {  
    int cnt = 1;  
    for(int i=1; i<=n; i++) {  
        if(height[i] >= mid) {  
            cnt ++;  
        } else cnt = 1;  
        if(cnt >= k) return true;  
    }  
    return false;  
}  
int xx[N],x[N];  
int search(int v,int m) {  
    int l = 0,r = m-1;  
    while(l <= r) {  
        int mid = (l + r) /2;  
        if(x[mid] == v)  
            return mid;  
        if(v < x[mid])  
            r = mid-1;  
        else  
            l = mid+1;  
    }  
    return -1;  
}  
int main() {  
    int n,k;  
    cin >> n >> k;  
    for(int i=0; i<n; i++) {  
        scanf("%d",&x[i]);  
        xx[i] = x[i];  
    }  
    int m = 1;  
    for (int i=1; i<n; i++) { //離散化去重   
        if (x[i] != x[i-1]) x[m ++] = x[i];  
    }  
    sort(x,x+m);  
    for(int i=0; i<n; i++) r[i] = search(xx[i],m) + 1;  
//    for(int i=0; i<n; i++) cout << r[i] << ' ';   
//    cout << endl;   
    r[n] = 0; //要保證結尾最小   
    dc3(r,sa,n+1,20001);  
    calheight(r,sa,n);  
    int l=1, r=n,mid; //枚舉長度   
    int ans = 0;  
    while(l <= r) {  
        mid = (l+r) >> 1;  
        if(judge(mid,n,k)) {  
            ans = mid;  
            l = mid + 1;  
        } else {  
            r = mid - 1;  
        }  
    }  
    cout << ans << endl;  
    return 0;  
}  

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 22222
#define INF 0x7FFFFFFF
/****後綴數組模版****/
#define F(x)((x)/3+((x)%3==1?0:tb)) //F(x)求出原字符串的suffix(x)在新的字符串中的起始位置
#define G(x)((x)<tb?(x)*3+1:((x)-tb)*3+2) //G(x)是計算新字符串的suffix(x)在原字符串中的位置，和F(x)為互逆運算
int wa[N],wb[N],wv[N],WS[N];
int sa[N*3] ; //第i小的後綴，起始位置在源字符串的位置
int rank1[N],height[N]; //rank 以i為起始位置的後綴在後綴排列中的名次
int r[N*3]; //如果輸入是字符串，承接字符串，用來計算


int c0(int *r,int a,int b) {
    return r[a]==r[b] && r[a+1]==r[b+1] && r[a+2]==r[b+2];
}
int c12(int k,int *r,int a,int b) {
    if(k==2)
        return r[a]<r[b] || ( r[a]==r[b] && c12(1,r,a+1,b+1) );
    else
        return r[a]<r[b] || ( r[a]==r[b] && wv[a+1]<wv[b+1] );
}
void sort(int *r,int *a,int *b,int n,int m) {
    int i;
    for(i=0; i<n; i++)
        wv[i]=r[a[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--)
        b[--WS[wv[i]]]=a[i];
    return;
}

//注意點：為了方便下面的遞歸處理，r數組和sa數組的大小都要是3*n
void dc3(int *r,int *sa,int n,int m) { //rn數組保存的是遞歸處理的新字符串，san數組是新字符串的sa
    int i , j , *rn = r+n , *san = sa+n , ta = 0 ,tb = (n+1)/3 , tbc = 0 , p;
    r[n] = r[n+1] = 0;
    for(i=0; i<n; i++) {
        if(i%3!=0)
            wa[tbc++]=i; //tbc表示起始位置模3為1或2的後綴個數
    }
    sort(r+2,wa,wb,tbc,m);
    sort(r+1,wb,wa,tbc,m);
    sort(r,wa,wb,tbc,m);
    for(p=1,rn[F(wb[0])]=0,i=1; i<tbc; i++)
        rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
    if(p<tbc)
        dc3(rn,san,tbc,p);
    else {
        for(i=0; i<tbc; i++)
            san[rn[i]]=i;
    }
//對所有起始位置模3等於0的後綴排序
    for(i=0; i<tbc; i++) {
        if(san[i]<tb)
            wb[ta++]=san[i]*3;
    }
    if(n%3==1)  //n%3==1，要特殊處理suffix(n-1)
        wb[ta++]=n-1;
    sort(r,wb,wa,ta,m);
    for(i=0; i<tbc; i++)
        wv[wb[i] = G(san[i])]=i;
//合並所有後綴的排序結果，保存在sa數組中
    for(i=0,j=0,p=0; i<ta&&j<tbc; p++)
        sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
    for(; i<ta; p++)
        sa[p]=wa[i++];
    for(; j<tbc; p++)
        sa[p]=wb[j++];
    return;
}

//height[i]=suffix(sa[i-1])和suffix(sa[i])的最長公共前綴，也就是排名相鄰的兩個後綴的最長公共前綴
void calheight(int *r,int *sa,int n) {
    int i,j,k=0;
    for(i=1; i<=n; i++)
        rank1[sa[i]]=i;
    for(i=0; i<n; height[rank1[i++]]=k)
        for(k?k--:0,j=sa[rank1[i]-1]; r[i+k]==r[j+k]; k++);
}

bool judge(int mid,int n,int k) {
    int cnt = 1;
    for(int i=1; i<=n; i++) {
        if(height[i] >= mid) {
            cnt ++;
        } else cnt = 1;
        if(cnt >= k) return true;
    }
    return false;
}
int xx[N],x[N];
int search(int v,int m) {
    int l = 0,r = m-1;
    while(l <= r) {
        int mid = (l + r) /2;
        if(x[mid] == v)
            return mid;
        if(v < x[mid])
            r = mid-1;
        else
            l = mid+1;
    }
    return -1;
}
int main() {
    int n,k;
    cin >> n >> k;
    for(int i=0; i<n; i++) {
        scanf("%d",&x[i]);
        xx[i] = x[i];
    }
    int m = 1;
    for (int i=1; i<n; i++) { //離散化去重
        if (x[i] != x[i-1]) x[m ++] = x[i];
    }
    sort(x,x+m);
    for(int i=0; i<n; i++) r[i] = search(xx[i],m) + 1;
//    for(int i=0; i<n; i++) cout << r[i] << ' ';
//    cout << endl;
    r[n] = 0; //要保證結尾最小
    dc3(r,sa,n+1,20001);
    calheight(r,sa,n);
    int l=1, r=n,mid; //枚舉長度
    int ans = 0;
    while(l <= r) {
        mid = (l+r) >> 1;
        if(judge(mid,n,k)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}