盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU5157 Harry and magic string(Manacher+差分前缀)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5157

题意

有一个字符串s,问有多少对子串对(suba, subb),使得suba和subb均为回文子串,且两个子串不能有重叠部分。

思路

首先可以用Manacher算法预处理出以每个字符(包括两个字符之间的位置)为中心能有多少个回文串。然后用差分前缀处理处pre、suf、sum三个数组。
其中pre数组表示到以某个字符结尾的回文串个数,suf表示以某个字符为开头的回文串个数,sum表示以某个字符之后的所有字符为开头的回文串个数。

代码

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define INF 1 << 30
#define fi first
#define se second
#define debug puts("=====================");
using namespace std;
typedef long long ll;
const int N = 210000;
char s[N], str[N];
int n, p[N];
void KP(int len, char *str) {
for (int i = 0; i < len; i++) {
s[2 * i + 1] = '#';
s[2 * i + 2] = str[i];
}
int n = 2 * len;
s[0] = s[n + 1] = '#';
s[n + 2] = 0;
int mx = 0, id;
for (int i = 1; i <= n; i++) {
if (mx > i) p[i] = min(p[2 * id - i], mx - i);
else p[i] = 1;
while(s[i + p[i]] == s[i - p[i]]) p[i]++;
if (p[i] + i > mx) {
mx = p[i] + i;
id = i;
}
}
}
ll pre[N / 2], suf[N / 2], sum[N / 2];
int main () {
while(~scanf("%s", str)) {
int len = strlen(str);
KP(len, str);
for (int i = 0; i <= len + 1; i++) pre[i] = suf[i] = sum[i] = 0;
for (int i = 2; i <= 2 * len; i++) {
int x = i / 2;
if (i % 2 == 0) pre[x]++, pre[x + (p[i] / 2)]--;
else pre[x + 1]++, pre[x + (p[i] / 2) + 1]--;
}
for (int i = 2 * len; i >= 2; i--) {
int x = i / 2;
if (i % 2 == 0) suf[x]++, suf[x - (p[i] / 2)]--;
else suf[x]++, suf[x - (p[i] / 2)]--;
}
for (int i = len; i >= 1; i--) {
suf[i] += suf[i + 1];
sum[i] += sum[i + 1] + suf[i];
}
ll ans = 0;
for (int i = 1; i <= len; i++) {
pre[i] += pre[i - 1];
ans += (ll)pre[i] * (sum[i + 1]);
}
printf("%I64d\n", ans);
}
return 0;
}