Ela的回文串：Hash写法

回文串：Hash写法"/>

Ela的回文串：Hash写法

题目🔗：Ela的回文串

看了巨巨们的写法，都是manacher。
可是我不会
但HASH大法好！献上hash写法！！！

前置知识

• 二分法（题目集在这里）
• hash字符串（hash经典题目）

你要的都在注释里

/** @Autor: Kadia* @Date: 2020-11-08 16:22:20* @LastEditors: Kadia* @Connect: 544692713@qq* @LastEditTime: 2020-11-08 17:59:56*/
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
char s[1005];
unsigned long long hashs[1005]; 
//正向hash，hashs[i]表示从第一个字符到i位置的hash值
unsigned long long rhashs[1005];
//逆向hash，rhashs[i]表示从第最后一个个字符到i位置的hash值
int vis[1005];
//正向最长喜欢长度，vis[i]表示从i向前的喜欢串的长度
int rvis[1005];
//逆向最长喜欢长度，rvis[i]表示从i向后的喜欢串的长度
int p=1333331; //hash常数
int len;       //输入的字符串的长度bool check(char x) //判断字符x是否是喜欢的字符
{if(x=='A'||x=='H'||x=='I'||x=='M'||x=='O'||x=='T'||x=='U'||x=='V'||x=='W'||x=='X'||x=='Y')return true;return false;
}bool check(int mid,int op)
/*
判断字符串是含有回文串的其中一半长度为mid的回文串，这里是一半是向上取整
*如ABBA的mid最大是2，ABA是mid最大也是2
*这里的op是一种状态符号，0表示所check的是偶数串如ABBA，1表示所check的是奇数串如ABA
*/
{unsigned long long Pow=1;for(int i=1;i<=mid;i++)Pow*=p;for(int i=mid-1;i+mid-op<len;i++){if(vis[i]<mid||rvis[i+(!op)]<mid)continue;unsigned long long tmp1,tmp2;if(i-mid<0)tmp1=hashs[i];elsetmp1=hashs[i]-hashs[i-mid]*Pow;tmp2=rhashs[i+(!op)]-rhashs[i+(!op)+mid]*Pow;if(tmp1==tmp2)return true;}return false;
}void Hash()//构建hash值
{hashs[0]=s[0];for(int i=1;i<len;i++)hashs[i]=hashs[i-1]*p+s[i];rhashs[len]=0;for(int i=len-1;i>=0;i--)rhashs[i]=rhashs[i+1]*p+s[i];
}void Vis()//构建vis数组
{vis[0]=check(s[0]);for(int i=1;i<len;i++){if(check(s[i]))vis[i]=vis[i-1]+1;elsevis[i]=0;}rvis[len]=0;for(int i=len-1;i>=0;i--){if(check(s[i]))rvis[i]=rvis[i+1]+1;elservis[i]=0;}
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%s",s);len=strlen(s);Hash();Vis();int l=0,r=(len+1)/2,mid,ans;while(l<=r){mid=(l+r)>>1;if(check(mid,0))  //判断是否有半串长度为mid的偶数串{ans=mid*2;l=mid+1;}else if(check(mid,1)) //判断是否有半串长度为mid的奇数串{ans=mid*2-1;l=mid+1;}elser=mid-1;}printf("%d\n",ans);}return 0;
}