[PKU/POJ][3261][Milk Patterns][后缀数组]

题目意思可以归结为给一个字符串，求可重叠的 k 次最长重复子串。

二分 k ，然后在 height 数组中找是否存大连续 k 个数都大于  k。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int const N= 1000100;
int wa[N], wb[N], ws[N], wv[N];
int rank[N], sa[N], height[N], r[N], n, k;

int cmp( int* r, int a, int b, int L ){
    return r[a]== r[b] && r[a+ L]== r[b+ L];
}

void da( int* r, int* sa, int n, int m ){
    int i, j, p, *x= wa, *y= wb, *t;
    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];
    for( i= n- 1; i>= 0; i-- ) sa[ --ws[ 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 ) 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];

        t= x, x= y, y= t, p= 1; x[ sa[0] ]= 0;
        for( i= 1; i< n; ++i )
            x[ sa[i] ]= cmp( y, sa[i-1], sa[i], j )? p- 1: p++;
    }
}

void callheight( int* r, int*sa, int n ){
    int i, j, k= 0;
    for( i= 1; i<= n; ++i ) rank[ sa[i] ]= i;

    for( i= 0; i< n; height[ rank[i++] ]= k )
        for( k?k--:0, j= sa[ rank[i]- 1]; r[i+k]== r[j+k]; k++ );

}

int Check( int mid ){
    int ans= 1;
    for( int i= 1; i<= n; ++i ){
        if( height[i]< mid ) ans= 1;
        else ans++;

        if( ans>= k ) return 1;
    }
    return 0;
}

int main(){
    scanf("%d%d",&n,&k );
    for( int i= 0; i< n; ++i ){
        scanf("%d", r+ i ); r[i]++;
    }
    r[n]= 0;
    da( r, sa, n+ 1, 1000002 );
    callheight( r, sa, n );

    int left= 1, right= n;
    while( left<= right ){
        int mid= (left+ right)>>1;

        if( Check( mid ) ) left= mid+ 1;
        else right= mid- 1;
    }
    printf("%d\n", right );

    return 0;
}