【hihocoder】 1721 回文字符串2

地址

https://hihocoder.com/problemset/problem/1721

题目

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 愚人节那天,小Ho在小Hi的一个回文字符串中添加了一个字符。你能帮助小Hi找到被添加的是第几个字符吗?

输入 一个只包含小写字母的字符串S。 对于70%的数据,|S| ≤ 1000
对于100%的数据,|S| ≤ 500000 输出 输出一个整数K,表示删除第K(从1开始计数)个字符后,S会变成一个回文字符串。
数据保证有解。如果有多个解,输出其中K最小的。

样例输入 aaba 样例输出 1

思路

  1. 思维("正解") 因为题目保证有解,删除某一个字符后字符串回文。所以可以从两端向中间扫,出现不对称的字符时枚举下删除的是左右哪边的,注意如果是相连的相同字符时要删除靠左的
  2. hash("邪教") 暴力从左到右枚举要删除的字符,利用hash比较删除后的是否相等。(写完就觉得不对劲,当时觉得这种hash不简单啊,怎么有人过的这么快!!!)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//hash邪教代码
#include <bits/stdc++.h>

using namespace std;

#define MP make_pair
#define PB push_back
typedef long long LL;
typedef unsigned int UU;
typedef pair<int,int> PII;
const double eps=1e-8;
const double pi=acos(-1.0);
const int K=5e5+7;
const int mod=1e9+7;


UU hs1[K],hs2[K],p[K],base;
char ss[K];

UU get_hash1(int l,int r)
{
if(l>r) return 0;
return hs1[r]-hs1[l-1]*p[r-l+1];
}
UU get_hash2(int l,int r)
{
if(l>r) return 0;
return hs2[l]-hs2[r+1]*p[r-l+1];
}

int main(void)
{
int ans=0;
base=mod;
scanf("%s",ss+1);
p[0]=1;
for(int i=1;i<K;i++)
p[i]=p[i-1]*base;
int len=strlen(ss+1),mid=(len-1)/2;
for(int i=1;i<=len;i++)
hs1[i]=hs1[i-1]*base+ss[i]-'a';
for(int i=len;i;i--)
hs2[i]=hs2[i+1]*base+ss[i]-'a';
for(int i=1;i<=len;i++)
if(len&1)
{
UU ta,tb;
if(i<=mid)
{
ta=get_hash1(1,i-1)*p[mid-i+1]+get_hash1(i+1,mid+1);
tb=get_hash2(mid+2,len);
}
else if(i==mid+1)
{
ta=get_hash1(1,mid);
tb=get_hash2(mid+2,len);
}
else
{
ta=get_hash1(1,mid);
tb=get_hash2(mid+2,i-1)+get_hash2(i+1,len)*p[i-1-mid-2+1];
}
if(ta==tb)
{
ans=i;break;
}
}
else
{
UU ta,tb;
if(i<=mid)
{
ta=get_hash1(1,i-1)*p[mid+1-i]+get_hash1(i+1,mid+1);
tb=get_hash2(mid+3,len);
}
else if(i==mid+1||i==mid+2)
{
ta=get_hash1(1,mid);
tb=get_hash2(mid+3,len);
}
else
{
ta=get_hash1(1,mid);
tb=get_hash2(mid+2,i-1)+get_hash2(i+1,len)*p[i-1-mid-2+1];
}
if(ta==tb)
{
ans=i;break;
}
}
printf("%d\n",ans);
return 0;
}