[CCPC2022湖北省赛]J. Palindrome Reversion(字符串hash)

发布于 2022-05-22  1350 次阅读


题目链接:https://codeforces.com/gym/103729/problem/J

赛场上没做出这题,可惜了。其实一开始就想到了字符串hash,甚至思路都和题解一样,但是由于忘记了字符串hash的板子,然后一时着急就没做出来。其实不难。

题意

给定一个字符串S,问能否通过将一个连续区间[l ,r](l <= r)翻转一次使得字符串S变为一个回文串。

输出任意一种可行方案即可。

如果不存在就输出-1 -1。

思路

第一步,如果这个字符串本身就是回文就不需要修改,直接输出1 1就行。

第二步,将字符串左右两边的回文部分删除,记录下删除了多少(记录为dl),输出答案的时候需要补上。

第三步,将当前字符串S初始化成hash串,要做两个hash,一个正向一个反向,同时把进制数base求一下连续的幂(后面求子串的hash会用到)。

第四步,以1作起点,向右枚举终点,如果找到了一个区间翻转可以使得字符串变为回文,那么就直接输出。如果没有,再从N为终点,向左枚举起点,如果有答案也直接输出。记得加上dl。

为什么从1和N开始枚举呢,因为可以翻转变为回文的一定是以下三种情况。

如果没答案就输出-1 -1。

真实惨痛的经历,下次一定要带全板子!

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef unsigned long long ULL;
const ULL maxn = 1e5 + 9, base = 131;

ULL h1[maxn], h2[maxn], b[maxn];
char s[maxn];
int N = 0;

void initHash(char s[], int N)
{
	b[0] = 1;
	for(int i = 1;i <= N; ++ i)b[i] = b[i - 1] * base;
	for(int i = 1;i <= N; ++ i)h1[i] = h1[i - 1] * base + s[i];
	for(int i = N;i >= 1; -- i)h2[i] = h2[i + 1] * base + s[i];
}

ULL getHash1(int l,int r){return h1[r] - h1[l - 1] * b[r - l + 1];}
ULL getHash2(int l,int r){return h2[l] - h2[r + 1] * b[r - l + 1];}

bool isRe(int l,int r)//将[l, r]翻转是否回文 
{
	ULL res1 = getHash1(1, l - 1) * b[N - l + 1] + getHash2(l, r) * b[N - r] + getHash1(r + 1, N);
	ULL res2 = getHash2(r + 1, N) * b[r] + getHash1(l, r) * b[l - 1] + getHash2(1, l - 1);
	return res1 == res2;
}

signed main()
{
	cin >> s + 1;
	int l = 1, r = strlen(s + 1);
	while(l <= r && s[l] == s[r])l ++, r --;
	int dl = l - 1;
	if(l > r)return printf("1 1\n"), 0;
	
	for(int i = l;i <= r; ++ i)s[++ N] = s[i];
	s[N + 1] = '\0';
	initHash(s, N);
	for(int i = 1;i <= N; ++ i)if(isRe(1, i))return printf("%lld %lld\n", 1 + dl, i + dl), 0;
	for(int i = N;i >= 1; -- i)if(isRe(i, N))return printf("%lld %lld\n", i + dl, N + dl), 0;
	printf("-1 -1\n");
	return 0;
}