hdu 4763 Theme Section(扩展kmp+线段树)
hdu 4763 Theme Section(扩展kmp+线段树)
大家无视这篇博文吧，更优秀的解法在这里：
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 | 1using 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 ;}