Time Limit:?6 Sec??Memory Limit:?128 MB
Submit:?153??Solved:?11

SubmitStatusWeb Board

Description

蛤瑋向心儀的妹子送了一條項鏈,這條項鏈?zhǔn)怯尚懽帜笜?gòu)成的首尾相接的字符串,妹子看了看項鏈對蛤瑋說,"我希望它是對稱的",蛤瑋想了想之后決定,從項鏈上截取出一段,這段如果是回文的話那么妹子戴起來就是對稱的了.由于蛤瑋會魔法,他可以把項鏈上的某一個字母變成任意另一個字母,但由于魔力限制他最多只能變兩次,現(xiàn)在蛤瑋想知道他能截取出的項鏈的最長長度是多少.為了簡單,我們假設(shè)蛤瑋截取出的長度必須是奇數(shù).

?

Input

?

第一行整數(shù)T(1<=T<=10),表示數(shù)據(jù)組數(shù).

?

每組數(shù)據(jù)一個字符串s,表示項鏈,|s|<=100000.

?

Output

每組數(shù)據(jù)輸出一個數(shù),最長的截取長度.

?

Sample Input

1 abcdaaa

Sample Output

7

HINT

?

樣例串改變一個字母變成abcbaaa,整個項鏈便可轉(zhuǎn)成回文aabcbaa.

?

思路：（dzs教我的）。由于是循環(huán)的，那么將s變?yōu)閟s，類似用hash求以i為中心的最長回文的長度，對于每一個位置i，先二分到pos1，那么pos1-i-（i-pos1+i）為當(dāng)前的回文段，pos1-=2，相當(dāng)于修改一次操作，繼續(xù)二分到一個位置pos2.如此做兩次，就相當(dāng)于兩次修改操作

#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];elseh = 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\n", ans);}return 0; }/**************************************************************Problem: 1876User: atrpLanguage: C++Result: AcceptedTime:2676 msMemory:6208 kb ****************************************************************/ View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/orchidzjl/p/5483554.html

總結(jié)

以上是生活随笔為你收集整理的ZZULI 1876: 蛤玮的项链 Hash + 二分的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。