【题解】51nod-1814-Clarke and string

题目

链接

题意

每次询问两个串的本质不同的公共子回文串的数量。

题解

官方题解如下:

用manacher+hash或回文树把所有 \(O(n)\) 个回文串求出来后,记录下来,令第 \(i\) 个串的回文串集合为 \(p(i)\) ,总回文串个数为 \(m\).

解法2: 对于询问 \(a, b\) ,假设 \(size(p(a)) < size(p(b))\) .那么我们直接用 \(p(a)\) 中的串丢去 \(p(b)\) 看是否存在就好了.注意若两个串询问过就从表里查询就好了.

我们来证明这样做是 \(O(n^{1.5})\) 的.

对于询问中有回文串个数小于等于 \(\sqrt{m}\) 的串,显然单次询问是 \(O(\sqrt{m})\) 的.

对于询问中回文串个数均大于 \(\sqrt{m}\) 的串,这样的串不超过 \(\sqrt{m}\) 个,每个串最多查询 \(m\) 次,所以总体复杂度是 \(O(m^{1.5})\) .

所以总时间复杂度为 $O(n^{1.5}) $.

设串 \(a\)\(b\) 的回文子串个数分别为 \(f(a)\)\(f(b)\),那么需要做到查询的复杂度为 \(\min\{f(a), f(b)\}\)。可以对所有串建立回文自动机,查询就是在两个串的各两棵树上统计公共结点的个数。(其实把所有串都建在一个回文自动机上会更加方便一些(广义回文自动机)。)

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 1E5 * 3 + 100;

struct P {
P *t[26], *fa;
int len;
} pool[maxn], *pit = pool;

struct PAM {
int sz, n;
char* s;
P *last, *null, *s1, *s2;
P* N(int l) {
++sz;
FOR (i, 0, 26) pit->t[i] = null;
pit->fa = null;
pit->len = l;
return pit++;
}
void init(char* _s) {
s = _s;
s1 = null = pit;
last = N(0);
last->fa = s2 = N(-1);

FOR (i, 1, strlen(s + 1) + 1) ins(s[i] - 'a');
}
P* get_fa(P* x) {
while (s[n - 1 - x->len] != s[n]) x = x->fa;
return x;
}
void ins(int ch) {
++n;
P* p = get_fa(last);
if (p->t[ch] == null) {
P* np = N(p->len + 2);
np->fa = get_fa(p->fa)->t[ch];
p->t[ch] = np;
}
last = p->t[ch];
}
} a[maxn];

int dfs(P* u, P* v, P* uu, P* vv) {
int ret = 1;
FOR (i, 0, 26)
if (u->t[i] != uu && v->t[i] != vv)
ret += dfs(u->t[i], v->t[i], uu, vv);
return ret;
}

int n, Q, ans;
char s[maxn];
map<pair<int, int>, int> mp;
int main() {
cin >> n;
FOR (i, 0, n) {
scanf("%s", s + 1);
a[i].init(s);
}
cin >> Q;
while (Q--) {
int u, v; scanf("%d%d", &u, &v);
u ^= ans; v ^= ans; --u; --v;
if (a[u].sz > a[v].sz || (a[u].sz == a[v].sz && u > v)) swap(u, v);
auto it = mp.find({u, v});
if (it != mp.end()) ans = it->second;
else mp[{u, v}] = ans =
dfs(a[u].s1, a[v].s1, a[u].null, a[v].null) +
dfs(a[u].s2, a[v].s2, a[u].null, a[v].null) - 2;
printf("%d\n", ans);
}
}