2020CCPC河南省赛子串翻转回文串

 

 

****注意千万不要用自然溢出哈希，会被卡成**；

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset> 
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define PI  acos(-1)
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 6e5+5;
const int mod = 1e9 + 7; 
const int P = 131;
int n,m,k,len;
char s[maxn];
int p[maxn],fr[maxn],inv[maxn];

int get(int l,int r){
	return ((fr[r] - fr[l - 1] * p[r - l + 1] % mod) % mod + mod) % mod;
}
int geti(int l,int r){
	return ((inv[l] - inv[r + 1] * p[r - l + 1] % mod) % mod + mod) % mod;
}
bool check(int l,int r){
	int t = fr[len],tt = inv[1];
	//减去翻转位置原串的hash值加上翻转后的hash值，判断是否相同，相同即为回文串 
	t = ((t - get(l,r) * p[l - 1] % mod + geti(l,r) * p[l - 1] % mod) % mod + mod) % mod;
	tt = ((tt - geti(l,r) * p[len - r] % mod + get(l,r) * p[len - r] % mod) % mod + mod) % mod;
	return t == tt;
}

void solve(){
	cin >> s + 1;
	len = strlen(s + 1);
	p[0] = 1;
	fr[0] = 0;
	for(int i = 1 ; i <= len ; ++i ){
		p[i] = p[i - 1] * P % mod;
		fr[i] = (fr[i - 1] * P % mod + s[i]) % mod;
	} 
	inv[len + 1] = 0;
	for(int i = len ; i >= 1 ; --i ){
		inv[i] = (inv[i + 1] * P % mod + s[i] ) % mod;
	}
	//如果原串是回文串直接输出 
	if(fr[len] == inv[1]){
		cout << "Yes" << endl;
		return;
	}
	//找到第一个不同点 
	int t = 1;
	for(int i = 1 ; i <= len ; ++i ){
		if(s[i] != s[len - i + 1]){
			t = i;
			break;
		}
	}
	//分别以不同的两端点作为左端点和右端点，判断反转后是否符合 
	for(int i = t; i <= len - t + 1 ; ++i){
		int l = t,r = i,ll = i,rr = len - t + 1;
		if(check(l,r) || check(ll,rr)){
			cout << "Yes" << endl;
			return;
		}
	}
	cout << "No" << endl;
}

main(){
	IOS;
	int tt;
	cin >> tt;
	while(tt--)
	solve();
}

 

本文地址：https://blog.csdn.net/FriendA831143/article/details/110287183