ZZULI 1876: 蛤玮的项链 Hash + 二分

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

Description

蛤玮向心仪的妹子送了一条项链,这条项链是由小写字母构成的首尾相接的字符串,妹子看了看项链对蛤玮说,"我希望它是对称的",蛤玮想了想之后决定,从项链上截取出一段,这段如果是回文的话那么妹子戴起来就是对称的了.由于蛤玮会魔法,他可以把项链上的某一个字母变成任意另一个字母,但由于魔力限制他最多只能变两次,现在蛤玮想知道他能截取出的项链的最长长度是多少.为了简单,我们假设蛤玮截取出的长度必须是奇数.

Input

第一行整数T(1<=T<=10),表示数据组数.

每组数据一个字符串s,表示项链,|s|<=100000.

Output

每组数据输出一个数,最长的截取长度.

Sample Input

abcdaaa

Sample Output

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 = ;

const int N = ;

unsigned long long H1[N], H2[N], xp[N];

char s[N];

int n, m;

void initHash() {

    H1[n] = H2[n] = ;

    int t = ;

    for(int i = n - ; i >= ; --i) {

        H2[i] = H2[i + ] * x + s[i];

        H1[i] = H1[i + ] * x + s[t++];

    }

    xp[] = ;

    for(int i = ; i <= n; ++i) xp[i] = xp[i - ] * x;

}

unsigned long long getHash(int i, int L, int f) {

    unsigned long long h;

    if(f == )

        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 = ; i < m; ++i) s[i + m] = s[i];

    n = m << ;

    initHash();

}

int get(int i) {

    int L = , R = i + ;

    while(R - L > ) {

        int M = (L + R) >> ;

        if(n - i + M <= n && i +  + M <= n && getHash(n - i, M, ) == getHash(i + , M, ))

         L = M;

        else R = M;

    }

    return L;

}

int change(int i, int cen) {

    int L = , R = i + ;

    while(R - L > ) {

        int M = (L + R) >> ;

        if(n - i -  + M <= n &&  * cen - i + M <= n && getHash(n - i - , M, ) == getHash( * cen - i, M, ))

        L = M;

        else R = M;

    }

    return L;

}

int solve() {

    int pos1, pos2, pos3, ls1, ls2;

    if(m <= ) return m;

    int ans = ;

    for(int i = ; i < n; ++i)

    {

        int x = get(i);

        pos1 = i - x;

        if(x +  + i < n) pos1 -= ;

        ls1 = change(pos1, i);

        pos2 = pos1 - ls1 + ;

        if(pos2 ==  && i - pos2 + i +  < n) pos3 = ;

        else if(pos2 == ) pos3 = pos2;

        else {

            pos3 = pos2;

            if(i - pos2 + i +  < n) {

                pos2 -= ;

                ls2 = change(pos2, i);

                pos3 = pos2 - ls2 + ;

            }

        }

        ans = max(ans, (i - pos3) *  + );

    }

    return min(m, ans);

}

int main() {

 // freopen("in", "r", stdin);

    int _; scanf("%d", &_);

    while(_ --) {

        init();

        int ans = solve();

        if(ans %  == ) ans--;

        printf("%d\n", ans);

    }

    return ;

}

/**************************************************************

    Problem: 1876

    User: atrp

    Language: C++

    Result: Accepted

    Time:2676 ms

    Memory:6208 kb

****************************************************************/

秒客网