字符串hash

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();}
}