pku 3261

啊，好 郁闷，这应该就是不理解模板的带来的后果吧，用之前那个模板，写了好几遍，改了好几遍，一直wa，可是换一个模板就过了，之后还是用这个模板吧

题意倒是很简单，就是求出至少重复k次的最长子串

还是用二分的思想，找出一组后缀数目大于等于k的最大后缀即可

#include <stdio.h>   
#include <stdlib.h>   
#include <string.h>   
int const N= 20100;   
int wa[N], wb[N], ws[N*2], wv[N];   
int rank[N], sa[N], height[N], r[N], n, k,m;   
  
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 );  m=0; 
    for( int i= 0; i< n; ++i ){   
        scanf("%d", r+ i ); r[i]++; 
		if(r[i]>m) m=r[i];
    }   
    r[n]= 0;   
    da( r, sa, n+ 1, ++m );   
    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;   
}