ThinkingBear's Necklace

Thinking bear necklace

String hash2

this problem uses the spillover measure and bisect measure and is typetical

/*
这道题主要考点是 字符串哈希 和 二分法比较字符串
前者我不知道也没想到， 后者我虽然知道，但却因为没怎么认真用过，所以没想到
这道题感觉很有参考价值（对于以上两个知识点：
左右哈希是对字符串哈希的加强（也是对于自然溢出法的加强）
二分法比较字符串明显比直接比较好多了，以后要多多考虑二分法，分块思想，ST table ， 线段树 ... (当然还有很多我还没见过的)等等这些大大减小复杂度的算法
这些算法都可以是非常灵活的，看思考的深不深了
*/
#include 
#include 
#include 
#define LOCAL
using namespace std;

typedef unsigned long long ull;
 
const int maxn = 100005;
const int seed=1e9+7;
 
int n,m;
char str[2*maxn];
ull has[2*maxn],rhas[2*maxn],pw[2*maxn];

void init()
{
    // store the p^(r-l+1) 
    pw[0]=1;
    for(int i=1;i<=2*maxn;++i)
    {
        pw[i]=pw[i-1]*seed;
    }
}
 
void init_has()
{
    //the left and right hash table are more powerful 
    for(int i=1;i<2*n;++i)
    {
        has[i]=has[i-1]*seed+(str[i]-'a'+1);
    }
    rhas[2*n+1]=0;
    for(int i=2*n;i>0;--i)
    {
        rhas[i]=rhas[i+1]*seed+(str[i]-'a'+1);
    }
}

bool check_has(int a,int b,int c)
{
    //自然溢出版哈希公式（相比于正式的字符串哈希公式：hash=((hash[r]-hash[l-1]*p^(r-l+1))%MOD+MOD)%MOD  ,  MOD is omitted）： hash=hash[r]-hash[l-1]*p^(r-l+1)
    ull sum,rsum;
    rsum=rhas[b]-rhas[b+c]*pw[c];   // c(the exploratory len): b ~ b+c-1   ;  pw[c] -> p^(r-l+1)=p^c
    sum=has[a]-has[a-c]*pw[c];
    return rsum==sum;
}
 
int check(int a,int b,int c)
{
    int ret=0;
    for(int i=0;i<3;++i)    //three times of bisect
    {
        int l,r,mid,cnt=0;
        l=1,r=c;
        /*
        I just can say : Although I know the bisect, I didn't know how to and when to use it 
        the bisect is O(logn) and the compare one by one is O(n)
        so the core for me is this bisect measure .....
        */
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(check_has(a,b,mid))
            {
                l=mid+1;
                cnt=mid;
            }
            else
            {
                r=mid-1;
            }
        }
        ret+=cnt;
        if(cnt==c)break;    //if the now radius reaches the max value, break
        c-=cnt+1;           //Next, the c should be lessen (cnt + 1 [the magic])
        a-=cnt+1;           // a-> the new start point (the next of magic pos)
        b+=cnt+1;
        if(c<0)break;       //c==0 couldn't break: ret++ should be carried out if i<2 ;
        if(i<2)ret++;       // plus the time of carrying out magic 
    }
    return ret;
}

int main()
{
    #ifdef LOCAL
    freopen("input.txt","r",stdin);
    #endif
    int T;
    cin>>T;
    init();
    while(T--)
    {
        cin>>str+1; // save the input from str+1
        n=strlen(str+1);
        for(int i=n+1;i<=2*n;++i)
        {
            str[i]=str[i-n];
        }
        init_has();
        int ans=1;
        for(int i=n/2;i+n/2<=2*n;++i)
        {
            int x=min(i-1,2*n-i);//  i-1 -> the left of i  ;  2*n-i -> the right of i
            x=min(x,(n-1)/2);//whether n is even or odd, the max raidus is (n-1)/2  ;  so the x shouldn't exceed the max radius
            // Actually, after i is ( (n-1)/2+1<=i<=2*n-(n-1)/2 ), the above two sentences are useless ...
            x=check(i-1,i+1,x);
            ans=max(ans,x*2+1);
        }
        cout<