org网站建设资源搜索器
K - 子串翻转回文串
2020ccpc河南省赛
字符串哈希：将字符串变成x进制数
对公式的理解：
举个十进制数的例子：123456
h[1]=1；
h[2]=1*10+2=12;
h[3]=12*10+3=123;
h[4]=123*10+4=1234;
.........
h[i]=h[i-1]*x+a[i];
h[i]代表的恰巧是整个数的前缀
用p[i]表示进制数的 i 次方；
想要单取出3-5的子串的值345
步骤；
1，先取出前缀12345（q[5]）
2，再减去12000：(h[2]*1000);
取子串哈希值的公式为：h[r]-h[l-1] *(r-l+1);
本题思路：
去掉前缀后缀相同的部分，剩余的前缀或后缀必定要翻转一次
判法：正反跑一次哈希（下标不变权值翻转）
--------------------------------------> 正向权值整串s1
----------> 正向权值翻转部分s2
<---------- 反向权值翻转部分s3
<-------------------------------------- 正向权值整串s4
判法：比较翻转前与翻转后的整串的哈希制是否一样
long long get1(int l,int r)
{
if(l==0) return h1[r];
return ((h1[r]%mod-h1[l-1]*p[r-l+1]%mod)+mod)%mod;/*注意负数取模*/
}
求正向的字符串的hash值
long long get2(int l,int r)
{
return (h2[l]%mod-h2[r+1]*p[r-l+1]%mod+mod)%mod;
}
求反向的字符串的hash值
反向之后如12345中的5是最高位，如求1-3的话我们就应该让a[1]-a[4]*10的(r-l+1)次方
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1e9+7;
const int INF=0x3f3f3f3f;
const int N = 5e5+10;
int st[N];int ed[N];int p[N];
int base=131;
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
int get1(int l,int r)
{return (st[r]-st[l-1]*p[r-l+1]%mod+mod)%mod;
}
int get2(int l,int r)
{return (ed[l]-ed[r+1]*p[r-l+1]%mod+mod)%mod;
}
bool check(int l,int r,int len)
{int dex = (st[len] - get1(l, r) * p[len - r] % mod + get2(l, r) * p[len - r] % mod + mod) % mod;/*从s1中取出s2放入s3所得出整串的哈希值*/int dey = (ed[1] - get2(l, r) * p[l - 1] % mod + get1(l, r) * p[l - 1] % mod + mod) % mod;/*从s4中取出s3放入s2所得出整串的哈希值*/ return dex == dey;
}
void solve()
{string s;cin>>s;int len=s.size();s=" "+s;int f=1;for(int i=1;i<=len/2;i++){if(s[i]!=s[len-i+1]){f=0;break;}} if(f==1){cout<<"Yes"<<endl;return ;}else{int pos;for(int i=1;i<=len;i++){if(s[i]!=s[len-i+1]){pos=i;break;}}p[0]=1;for(int i=1;i<=len;i++){st[i]=(st[i-1]*base%mod+s[i])%mod; p[i]=p[i-1]*base%mod;}ed[len+1]=0;for(int j=len;j>=1;j--){ed[j]=(ed[j+1]*base%mod+s[j])%mod;}for(int i=pos;i<=len-pos+1;i++){int l=pos,r=i;int ll=i,rr=len-pos+1;if(check(l,r,len)||check(ll,rr,len)){cout<<"Yes"<<endl;return ;} } }cout<<"No"<<endl;
}
signed main()
{ios;int t;cin>>t;while(t--){solve();}
}