Three Palindromes（Mannacer算法）

题目链接：点击打开链接

题目大意：给出T个字符串，问每个字符串是不是由三个回文串组成，是输出Yes，否则No

n*n的复杂度竟然可以过啊，，，，，，，，

用Mannacer直接计算出以每一位为中心的最长回文串，然后求出pre[i](1～i)是否为回文串，suf[i](i～len-1)是否为回文串，然后枚举第二段回文串的中点，只要在第二段中左侧和右侧存在同样位置的两个pre[j]和suf[j]为1，那么就证明可以

注意：因为Mannacer会使得字符串长度增加一倍，枚举中点后，遍历回文串时只遍历字符，，不遍历‘#’。

#include <cstdio>#include <cstring>#include <algorithm>using namespace std ;#pragma comment(linker,"STACK:102400000,102400000") ;#define maxn 50000char str[maxn] , s[maxn] ;int p[maxn] ;int pre[maxn] , suf[maxn] ;int init() {int i = 0 , j = 0 , l = strlen(str) ;s[j++] = '$' ;while( i < l ) {s[j++] = '#' ;s[j++] = str[i] ;i++ ;}s[j++] = '#' ;s[j] = '\0' ;return j ;}void Manacer(int l) {int i , max1 = 0 , id ;for(i = 1 ; i < l ; i++) {if( max1 > i )p[i] = min( p[2*id-i],max1-1 ) ;elsep[i] = 1 ;while( s[i-p[i]] == s[i+p[i]] )p[i]++ ;if( p[i]+i > max1 ) {max1 = p[i]+i ;id = i ;}}}int solve(int i,int len) {int l , r , j , m ;l = i-p[i] ;r = i+p[i] ;if( i%2 ) m = i-1 ;else m = i ;j = max( r-len+2,2-l ) ;j = max(j,0) ;if( (l+j)%2 ) j++ ;for( ; l+j < m ; j += 2) {if( pre[l+j] && suf[r-j] ) break ;}if( l+j < m ) return 1 ;return 0 ;}int main() {int t , m , i , j , len , l , r ;scanf("%d", &t) ;while( t– ) {scanf("%s", str) ;len = init() ;Manacer(len) ;memset(pre,0,sizeof(pre)) ;memset(suf,0,sizeof(suf)) ;for(i = 1 ; i < len ; i++) {if( i-p[i]+1 == 1 )pre[ i+p[i]-2 ] = 1 ;else if( i-p[i]+1 == 2 )pre[ i+p[i]-1 ] = 1 ;if( i+p[i]-1 == len-1 )suf[ i-p[i]+2 ] = 1 ;else if( i+p[i]-1 == len-2 )suf[ i-p[i]+1 ] = 1 ;}for(i = 1 ; i <= len-i ; i++) {if( solve(i,len) ) break ;if( solve(len-i,len) ) break ;}if( i <= len-i )printf("Yes\n") ;elseprintf("No\n") ;}return 0 ;}

寂寞的人总是记住生命中出现的每一个人，

相关文章：

你感兴趣的文章：

标签云：