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

Posted on Edited on In Disqus:

题目

链接

题意

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

题解

官方题解如下：

用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);
    }
}