hdu 4763 Theme Section(扩展kmp+线段树)

大家无视这篇博文吧，更优秀的解法在这里：

题目大意：给出一个字符串，问这个字符串的最长Theme Section是多长，Theme Section要符合以下条件，必须出现在字符串的开头，结尾，和中间，而且不能有重叠。

解题思路：我们学校有队伍用的暴力kmp过的，我后来看了下他的代码，似乎是不行的。说说我的思路，我们扩展kmp求出一个next数组，next[i]表示以i为开头的后缀与该字符串的最长公共前缀的长度。然后从后往前枚举长度为i的后缀，若这个后缀与字符串的最长公共前缀等于i，那么它有可能成为答案，它要能成为答案，那么我们还要在[i,len-2*i]这个区间里找出一个后缀，这个后缀与字符串的最长公共前缀要大于等于i，这个最大值，我本来想用rmp预处理，然后o（1）回答，但是空间复杂度是过不了的，所以就用线段树询问好了。整体时间复杂度是o(nlogn)的，如果大数据不超过10组的话，应该是没问题的。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
using namespace std ;

const int maxn = 1111111 ;

int max ( int a , int b ) { return a > b ? a : b ; }

int p[maxn] ;
int mx[maxn<<2] ;

void get_p (const char *T){
     int len=strlen(T),a=0;
     int i , k ;
     p[0]=len;
     while(a<len-1 && T[a]==T[a+1]) a++;
     p[1]=a;
     a=1;
     for( k=2;k<len;k++){
         int fuck=a+p[a]-1,L=p[k-a];
         if( (k-1)+L >= fuck){
             int j = (fuck-k+1)>0 ? (fuck-k+1) : 0;
             while(k+j<len && T[k+j]==T[j]) j++;
             p[k]=j;
             a=k; 
         } 
         else p[k]=L; 
     }
}

inline void push_up ( int rt ) {
    mx[rt] = max ( mx[rt<<1] , mx[rt<<1|1] ) ;
}

void build ( int l , int r , int rt ) {
    if ( l == r ) {
        mx[rt] = p[l] ;
        return ;
    }
    int m = ( l + r ) >> 1 ;
    build ( lson ) ;
    build ( rson ) ;
    push_up ( rt ) ;
}

int query ( int a , int b , int l , int r , int rt ) {
    if ( a <= l && r <= b ) return mx[rt] ;
    int m = ( l + r ) >> 1 ;
    int ret = 0 ;
    if ( a <= m ) ret = query ( a , b , lson ) ;
    if ( m < b ) ret = max ( ret , query ( a , b , rson ) ) ;
    return ret ;
}

char s[maxn] ;

int main () {
    int t , i ;
    scanf ( "%d" , &t ) ;
    while ( t -- ) {
        scanf ( "%s" , s ) ;
        get_p ( s ) ;
        int n = strlen ( s ) ;
        build ( 0 , n - 1 , 1 ) ;
        int ans = 0 ;
        for ( i = 1 ; i <= n / 3 ; i ++ ) {
            if ( p[n-i] == i ) {
                if ( query ( i , n - ( 2 * i ) ,  0 , n - 1 , 1 ) >= i ) ans = i ;
            }
        }
        printf ( "%d\n" , ans ) ;
    }
    return 0 ;
}

秒客网

hdu 4763 Theme Section(扩展kmp+线段树)

相关文章