Submit: 153 Solved: 11
SubmitStatusWeb Board
Description
蛤玮向心仪的妹子送了一条项链,这条项链是由小写字母构成的首尾相接的字符串,妹子看了看项链对蛤玮说,"我希望它是对称的",蛤玮想了想之后决定,从项链上截取出一段,这段如果是回文的话那么妹子戴起来就是对称的了.由于蛤玮会魔法,他可以把项链上的某一个字母变成任意另一个字母,但由于魔力限制他最多只能变两次,现在蛤玮想知道他能截取出的项链的最长长度是多少.为了简单,我们假设蛤玮截取出的长度必须是奇数.
Input
第一行整数T(1<=T<=10),表示数据组数.
每组数据一个字符串s,表示项链,|s|<=100000.
Output
每组数据输出一个数,最长的截取长度.
Sample Input
1
abcdaaa
Sample Output
7
HINT
样例串改变一个字母变成abcbaaa,整个项链便可转成回文aabcbaa.
思路：（dzs教我的）。由于是循环的，那么将s变为ss，类似用hash求以i为中心的最长回文的长度，对于每一个位置i，先二分到pos1，那么pos1-i-（i-pos1+i）为当前的回文段，pos1-=2，相当于修改一次操作，继续二分到一个位置pos2.如此做两次，就相当于两次修改操作
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <map> #include <string> using namespace std; const int x = 123; const int N = 200005; unsigned long long H1[N], H2[N], xp[N]; char s[N]; int n, m; void initHash() { H1[n] = H2[n] = 0; int t = 0; for(int i = n - 1; i >= 0; --i) { H2[i] = H2[i + 1] * x + s[i]; H1[i] = H1[i + 1] * x + s[t++]; } xp[0] = 1; for(int i = 1; i <= n; ++i) xp[i] = xp[i - 1] * x; } unsigned long long getHash(int i, int L, int f) { unsigned long long h; if(f == 1) h = H1[i] - H1[i + L] * xp[L]; else h = H2[i] - H2[i + L] * xp[L]; return h; } void init() { scanf("%s", s); m = strlen(s); for(int i = 0; i < m; ++i) s[i + m] = s[i]; n = m << 1; initHash(); } int get(int i) { int L = 0, R = i + 1; while(R - L > 1) { int M = (L + R) >> 1; if(n - i + M <= n && i + 1 + M <= n && getHash(n - i, M, 1) == getHash(i + 1, M, 2)) L = M; else R = M; } return L; } int change(int i, int cen) { int L = 0, R = i + 2; while(R - L > 1) { int M = (L + R) >> 1; if(n - i - 1 + M <= n && 2 * cen - i + M <= n && getHash(n - i - 1, M, 1) == getHash(2 * cen - i, M, 2)) L = M; else R = M; } return L; } int solve() { int pos1, pos2, pos3, ls1, ls2; if(m <= 5) return m; int ans = 5; for(int i = 3; i < n; ++i) { int x = get(i); pos1 = i - x; if(x + 2 + i < n) pos1 -= 2; ls1 = change(pos1, i); pos2 = pos1 - ls1 + 1; if(pos2 == 1 && i - pos2 + i + 1 < n) pos3 = 0; else if(pos2 == 0) pos3 = pos2; else { pos3 = pos2; if(i - pos2 + i + 2 < n) { pos2 -= 2; ls2 = change(pos2, i); pos3 = pos2 - ls2 + 1; } } ans = max(ans, (i - pos3) * 2 + 1); } return min(m, ans); } int main() { // freopen("in", "r", stdin); int _; scanf("%d", &_); while(_ --) { init(); int ans = solve(); if(ans % 2 == 0) ans--; printf("%d ", ans); } return 0; } /************************************************************** Problem: 1876 User: atrp Language: C++ Result: Accepted Time:2676 ms Memory:6208 kb ****************************************************************/