浙江建设技术职业学院网站,资源网站模板,有限公司名称大全,成都网站app开发K - 子串翻转回文串2020ccpc河南省赛字符串哈希#xff1a;将字符串变成x进制数对公式的理解#xff1a;举个十进制数的例子#xff1a;123456h[1]1#xff1b;h[2]1*10212;h[3]12*103123;h[4]123*1041234;.........h[i]h[i-1]*xa[i];h[i]代表的恰巧是整个数的前缀用p[i]表…K - 子串翻转回文串2020ccpc河南省赛字符串哈希将字符串变成x进制数对公式的理解举个十进制数的例子123456h[1]1h[2]1*10212;h[3]12*103123;h[4]123*1041234;.........h[i]h[i-1]*xa[i];h[i]代表的恰巧是整个数的前缀用p[i]表示进制数的 i 次方想要单取出3-5的子串的值345步骤1先取出前缀12345q[5]2再减去12000(h[2]*1000);取子串哈希值的公式为h[r]-h[l-1] *(r-l1);本题思路去掉前缀后缀相同的部分剩余的前缀或后缀必定要翻转一次判法正反跑一次哈希下标不变权值翻转-------------------------------------- 正向权值整串s1 ---------- 正向权值翻转部分s2 ---------- 反向权值翻转部分s3-------------------------------------- 正向权值整串s4判法比较翻转前与翻转后的整串的哈希制是否一样long long get1(int l,int r){if(l0) return h1[r];return ((h1[r]%mod-h1[l-1]*p[r-l1]%mod)mod)%mod;/*注意负数取模*/}求正向的字符串的hash值long long get2(int l,int r){return (h2[l]%mod-h2[r1]*p[r-l1]%modmod)%mod;}求反向的字符串的hash值反向之后如12345中的5是最高位如求1-3的话我们就应该让a[1]-a[4]*10的(r-l1)次方#includebits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define YES coutYESendl
#define NO coutNOendl
typedef long long ll;
typedef pairint,int PII;
const ll mod1e97;
const int INF0x3f3f3f3f;
const int N 5e510;
int st[N];int ed[N];int p[N];
int base131;
#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-l1]%modmod)%mod;
}
int get2(int l,int r)
{return (ed[l]-ed[r1]*p[r-l1]%modmod)%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;cins;int lens.size();s s;int f1;for(int i1;ilen/2;i){if(s[i]!s[len-i1]){f0;break;}} if(f1){coutYesendl;return ;}else{int pos;for(int i1;ilen;i){if(s[i]!s[len-i1]){posi;break;}}p[0]1;for(int i1;ilen;i){st[i](st[i-1]*base%mods[i])%mod; p[i]p[i-1]*base%mod;}ed[len1]0;for(int jlen;j1;j--){ed[j](ed[j1]*base%mods[j])%mod;}for(int ipos;ilen-pos1;i){int lpos,ri;int lli,rrlen-pos1;if(check(l,r,len)||check(ll,rr,len)){coutYesendl;return ;} } }coutNoendl;
}
signed main()
{ios;int t;cint;while(t--){solve();}
}
