HDU 5658 CA Loves Palindromic(Manacher | 回文树)

题意:

$N\le 10^3的字符串,Q\le 10^5次询问$
$每次询问[l, r]区间本质不同的回文子串有几个,即不完全相同的回文子串$

分析:

$Manacher做法,就离线询问,然后判断回文,哈希判重$
$回文树就更暴力了,直接预处理ans[l][r]$
$回文树的学习直接上鸟神博客$,Palindromic Tree——回文树【处理一类回文串问题的强力工具】

Manacher代码:

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
//
// Created by TaoSama on 2016-04-08
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e3 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
struct BIT {
int n, b[N];
void init(int _n) {
n = _n;
memset(b, 0, sizeof b);
}
void add(int i, int v) {
for(; i; i -= i & -i) b[i] += v;
}
int sum(int i) {
int ret = 0;
for(; i <= n; i += i & -i) ret += b[i];
return ret;
}
} bit;
struct Manacher {
char s[N << 1];
int n, p[N << 1];
void init(char* a) {
s[0] = '@'; s[1] = '#'; n = 2;
for(int i = 1; a[i]; ++i)
s[n++] = a[i], s[n++] = '#';
s[n] = 0;
}
int gao() {
int mx = 0, id, ret = 0;
for(int i = 1; i < n; ++i) {
p[i] = mx > i ? min(mx - i, p[2 * id - i]) : 1;
while(s[i - p[i]] == s[i + p[i]]) ++p[i];
if(mx < i + p[i]) mx = i + p[i], id = i;
ret = max(ret, p[i] - 1);
}
return ret;
}
bool ok(int l, int r) {
l <<= 1; r <<= 1;
int k = l + r >> 1;
return k + p[k] - 1 >= r;
}
} manacher;
typedef unsigned long long ULL;
const ULL seed[2] = {MOD, MOD + 2};
struct Hash {
typedef pair<ULL, ULL> Type;
ULL power[2][N], h[2][N];
void init(char* a) {
for(int i = 0; i < 2; ++i) {
power[i][0] = 1; h[i][0] = 0;
for(int j = 1; a[j]; ++j) {
power[i][j] = power[i][j - 1] * seed[i];
h[i][j] = h[i][j - 1] * seed[i] + a[j];
}
}
}
Type get(int l, int r) { // [l, r]
Type ret;
ret.first = h[0][r] - h[0][l - 1] * power[0][r - l + 1];
ret.second = h[1][r] - h[1][l - 1] * power[1][r - l + 1];
return ret;
}
} hsh;
int n, q;
const int Q = 1e5 + 10;
int ans[Q];
char a[N];
vector<pair<int, int> > qs[N];
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
int t; scanf("%d", &t);
while(t--) {
scanf("%s", a + 1);
n = strlen(a + 1);
hsh.init(a);
manacher.init(a);
manacher.gao();
scanf("%d", &q);
for(int i = 1; i <= n; ++i) qs[i].clear();
for(int i = 1; i <= q; ++i) {
int l, r; scanf("%d%d", &l, &r);
qs[r].push_back({l, i});
}
bit.init(n);
map<Hash::Type, int> mp;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= i; ++j) {
if(!manacher.ok(j, i)) continue; //not palindromic
Hash::Type h = hsh.get(j, i);
if(mp.count(h)) bit.add(mp[h], -1);
bit.add(j, 1);
mp[h] = j;
}
for(auto& q : qs[i]) ans[q.second] = bit.sum(q.first);
}
for(int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
}
return 0;
}

回文树代码:

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
94
95
96
97
98
99
100
101
102
103
104
105
106
//
// Created by TaoSama on 2016-04-08
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e3 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
// last:= 指向添加一个字符后形成的最长回文串的节点
// s[i]:= 第 i 次添加的字符 n:= s 数组时针
// fail[i]:= i 失配后跳转到的 i 表示的最长回文串的最长真后缀回文串的节点
// cnt[i]:= 以 i 表示的最长回文串的右端点为右端点的回文串个数
// dif[i]:= i 表示的本质不同的回文串个数 (需要重新统计)
struct PalindromicTree {
static const int M = 1e3 + 10, S = 26;
int n, sz, last;
int nxt[M][S], fail[M], len[M], s[M];
int cnt[M], dif[M];
int newNode(int l) {
len[sz] = l;
cnt[sz] = dif[sz] = 0;
memset(nxt[sz], 0, sizeof nxt[sz]);
return sz++;
}
void init() {
sz = last = 0;
newNode(0); newNode(-1);
s[n = 0] = -1; // 无关字符减少特判
fail[0] = 1;
}
int getFail(int u) {
while(s[n - len[u] - 1] != s[n]) u = fail[u];
return u;
}
void add(int c) {
s[++n] = c;
int u = getFail(last); // 找到这个回文串的匹配位置
int& v = nxt[u][c];
if(!v) {
int cur = newNode(len[u] + 2);
fail[cur] = nxt[getFail(fail[u])][c];
v = cur;
cnt[v] = cnt[fail[v]] + 1;
}
++dif[v];
last = v;
}
void count() {
//父亲累加儿子,如果 fail[v]=u ,则 u 一定是 v 的子回文串
for(int i = sz - 1; ~i; --i) dif[fail[i]] += dif[i];
}
} pt;
int n, q;
char a[N];
int ans[N][N];
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
int t; scanf("%d", &t);
while(t--) {
scanf("%s", a + 1);
n = strlen(a + 1);
for(int i = 1; i <= n; ++i) {
pt.init();
for(int j = i; j <= n; ++j) {
pt.add(a[j] - 'a');
ans[i][j] = pt.sz - 2;
}
}
scanf("%d", &q);
while(q--) {
int l, r; scanf("%d%d", &l, &r);
printf("%d\n", ans[l][r]);
}
}
return 0;
}


1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到