Three PalindromesTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 809Accepted Submission(s): 240
Problem Description
Can we divided a given string S into three nonempty palindromes?
Input
First line contains a single integer
which denotes the number of test cases.For each test case , there is an single line contains a string S which only consist of lowercase English letters.
Output
For each case, output the "Yes" or "No" in a single line.
Sample Input
2abcabaadada
Sample Output
YesNo
Source
BestCoder Round #49 ($)
Recommend
hujie
大致题意：
判断长度为2e4的字符串是否能分割成三个回文串
大致思路：
BC由于做出了这题，拿到钱了2333
然后折半枚举判a[x]~b[y]是不是回文串，用manacherO(1)就能判出来
Manacher算出了已s[x]为中心的最长回文串，然后反推到原串上的区间比较麻烦
以前推了一个公式，已经用这个公式过了三题了，说明的确没问题
int L = (i-Mp[i])>>1;int R = (i+Mp[i]-4)>>1;
//#pragma comment(linker, "/STACK:1024000000,1024000000")#include <iostream>#include <cstring>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#include <string>#include <vector>#include <cstdio>#include <ctime>#include <bitset>#include <algorithm>#define SZ(x) ((int)(x).size())#define ALL(v) (v).begin(), (v).end()#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)#define REP(i,n) for ( int i=1; i<=int(n); i++ )using namespace std;typedef long long ll;#define X first#define Y secondtypedef pair<int,int> pii;template <class T>inline bool RD(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void PT(T x){if (x < 0) {putchar('-');x = -x;}if (x > 9) pt(x / 10);putchar(x % 10 + '0');}const int N = 20000+100;int a[N],top1;int b[N],top2;char s[N];void ini(){top1 = 0;top2 = 0;}int Mp[N<<1];char Ma[N<<1];int vs[N];void Manacher(char s[],int len){int l = 0;Ma[l++] = '$';Ma[l++] = '#';for(int i=0;i<len;i++){Ma[l] = s[i];vs[i] = l++; //记录映射到原串中的位置Ma[l++] = '#';}Ma[l] = 0;int mx = 0,id = 0;for(int i = 1;i < l ;i ++){Mp[i]= mx>i? min(Mp[2*id-i],mx-i) :1;while(Ma[Mp[i]+i ] == Ma[i-Mp[i] ]) Mp[i]++;if(Mp[i]+i > mx){mx = Mp[i]+i;id = i;}if( Mp[i] >= 2){int L = (i-Mp[i])>>1; //逆推到原串中的区间左端点int R = (i+Mp[i]-4)>>1; //逆推到原串中的区间右端点if(L == 0) a[++top1] = R;if(R == len-1) b[++top2] = L;}}}int main(){int T;RD(T);while(T–){scanf("%s",s);ini();int len = strlen(s);Manacher(s,len);sort(a+1,a+1+top1);sort(b+1,b+1+top2);bool ok = 0;REP(i,top1) {if(ok) break;for(int j = top2; j >= 1 && ok == 0;j–){int l = a[i], r = b[j];if( r-l <= 1) break;l++,r–;if( (r-l+1)&1 ){int pos = l+(r-l+1)/2;int L = (vs[pos]-Mp[vs[pos]])>>1;int R = (vs[pos]+Mp[vs[pos]]-4)>>1;if( L <= l && r <= R) ok = 1;}else {int pos = l+(r-l+1)/2;int p = vs[pos]-1;if( Mp[p] < 2) continue;int L = (p-Mp[p])>>1;int R = (p+Mp[p]-4)>>1;if( L <= l && r <= R) ok = 1;}}}if(ok) puts("Yes");else puts("No");}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
蚁穴虽小，溃之千里。
