题目链接：?pid=5340
题意：判断一个字符串能否分为三个回文串
解法：manacher枚举第一第三个，，判断第二个。
代码：
;int t;int p[220100];char s[220100], c[221000];int pre[221000], last[221000];int solve(){int len = strlen(s);c[0] = ‘$’;for (int i = 0; i<len; i++)c[i * 2 + 1] = ‘#’, c[i * 2 + 2] = s[i];c[len * 2 + 1] = ‘#’;len = len * 2 + 2;c[len] = 0;int mx = 0, id = 0;for (int i = 1; i<len; i++){if (mx>i) p[i] = min(p[id * 2 – i], p[id] + id – i);else p[i] = 1;while (c[i + p[i]] == c[i – p[i]]) p[i]++;if (i + p[i]>mx) mx = i + p[i], id = i;}int p_num = 0, l_num = 0;for (int i = 2; i < len – 1; i++){if (i == p[i]) pre[p_num++] = i;if (i + p[i] == len) last[l_num++] = i;}for (int i = 0; i < p_num; i++){for (int j = l_num – 1; j >= 0; j–){int pos1 = pre[i] + p[pre[i]];int pos2 = last[j] – p[last[j]];if (pos1 > pos2) break;int mid = (pos1 + pos2) / 2;if (mid<=len-4)if (mid – pos1 + 1 <= p[mid]) return 1;}}return 0;}int main(){scanf(“%d”, &t);while (t–){scanf(“%s”, s);if (solve()) printf(“Yes\n”);else printf(“No\n”);}return 0;}
于是，月醉了，夜醉了，我也醉了。
