HDU5340 Three Palindromes < Manacher >

Posted on Symbols count in article: 530 Reading time ≈ 2 mins.

Problem

Three Palindromes

Description

Can we divided a given string SS into three nonempty palindromes?

Input

First line contains a single integer T≤20T\le 20 which denotes the number of test cases.
For each test case , there is an single line contains a string SS which only consist of lowercase English letters.1≤∣s∣≤200001\le |s|\le 20000

Output

For each case, output the Yes or No​ in a single line.

Sample Input

1
2
3
2
abc
abaadada

Sample Output

1
2
Yes
No

标签：Manacher

Translation

给出字符串SS，判断SS是否能被分为三段回文串。

Solution

看到回文串，可知本题大概和Manacher有关。
在Manacher中，我们有一个数组ff，f[i]f[i]记录从第i位向两边拓展，最长回文串的半径是多少。注意到本题有一个特殊的数据——33，而三段中，只要能确定任意两段，另一段就能确定。而这三段中肯定有两段是覆盖到串首或串尾的。因而我们可以用f[i]f[i]是否等于ii来确定ii位置是否能成为第一个段的中心点，如法炮制可求出第三段。这时我们暴力枚举第一段和第三段，这样确定第二段后，找到此段中心，可通过ff确定第二段是否是回文串。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_L 20000
using namespace std;
char s[MAX_L*2+5];
int f[MAX_L*2+5];
bool manacher (char* s0) {
    int len = strlen(s0), pos = 0, r = 0;
    for (int i = 0; i < len; i++)	s[i*2+1] = '#', s[i*2+2] = s0[i];	s[len = len*2+1] = '#';
    for (int i = 1; i <= len; i++) {
        f[i] = (i < r) ? min(f[2*pos-i], r-i) : 1;
        while (i-f[i] >= 1 && i+f[i] <= len && s[i-f[i]] == s[i+f[i]])	f[i]++;
        if (i+f[i] > r)	pos = i, r = i+f[i];
    }
    int lm[MAX_L*2+5], rm[MAX_L*2+5], cntl = 0, cntr = 0;
    for (int i = 1; i <= len; i++) {
        if (f[i] == i && f[i] > 1)	lm[cntl++] = i;
        if (f[len-i+1] == i && f[len-i+1] > 1)	rm[cntr++] = len-i+1;
    }
    for (int i = 0; i < cntl; i++)
        for (int j = 0; j < cntr; j++) {
            int s = lm[i]+f[lm[i]], t = rm[j]-f[rm[j]];
            if (s > t)	continue;
            if (f[s+t>>1] == 1)	continue;
            if (f[s+t>>1]*2-1 < t-s+1)	continue;
            return true;
        }
    return false;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        char s0[MAX_L+5];
        scanf("%s", s0);
        if (manacher(s0))	printf("Yes\n");
        else	printf("No\n");
    }
    return 0;
}