CTime_Pup_314

不能再颓废了

0%

[BZOJ3413]匹配

发表于 更新于 分类于 阅读次数： Valine：

题面描述

求 \(A\) 串对 \(B\) 串朴素匹配的比较次数

题解

一道综合性和思维性很好的题

解决的关键在于把匹配的复杂度转移到 \(A\) 上

起初没什么思路，只知道这道题一定是在 \(B\) 的 \(Parent\) 树上乱搞

对着样例和 \(Parent\) 树找了快半个小时的规律才知道怎么做

首先分两种情况讨论 第一种，\(A\) 可以匹配上 \(B\)，记匹配位置为 \(pos\)

那么答案即为

\[ \sum_{i=1}^{pos-1}[LCP(A,\ B[1,i])+1]+len(B) \]

我们在 \(B\) 的 \(SAM\) 上匹配 \(A\)，匹配上时的节点为 \(x\)，不难发现，\(pos\ =\ min\lbrace k\rbrace,k\in endpos(x)\)

考虑前面的式子如何求出，我们会发现正串的 \(Parent\) 树向上跳时方便求出的是 \(LCS\) 与该题结合十分不自然，所以不妨在反串上建 \(SAM\)，得出后缀树

在后缀树上向上跳，\(A\)和\(B\)前缀不断缩小，具有相同前缀的位置越来越多，正好与匹配过程相一致，具体来说，\(LCP\)即为相应位置第一次在向上跳相遇时 \(endpos\) 集合的最长长度，前面的式子用后缀树改写即为

\[ \sum_{i=1}^{pos-1}[maxlen(p_i)+1],\ \forall i\in p_k\ maxlen(p_i) \ge maxlen(p_k),\ p_i\in path(x,S) \]

所以我们只需要向上跳后缀树，每次加上该节点小于 \(pos\) 的 \(endpos\) 个数乘上该节点所表示字符串的长度区间长度即可，每个位置的贡献恰好按照上式不重不漏统计了一次，最后再加上 \(pos-1\) 即可，用线段树合并即可

第二种，\(A\) 匹配不上 \(B\) 那么答案即为

\[ \sum_{i=1}^{len(B)}[LCP(A,\ B[1,i])+1] \]

记匹配最后节点为 \(x\)，按照上述讨论，答案变为

\[ \sum_{i=1}^{len(B)}[maxlen(p_i)+1],\ \forall i\in p_k\ maxlen(p_i) \ge maxlen(p_k),\ p_i\in path(x,S) \]

然而答案错误，是由于 \(x\) 的贡献不一定是 \(maxlen(x)\)，有可能只是一部分，所以特殊统计一下就好了，与 [HAOI2016]找相同字符 类似

此题空间严格，需要仔细计算空间大小

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
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2e5+5;
typedef long long int64;
int n, m, q;
char s[N];
namespace sam
{
int tot = 1, last = 1, ch[N][10], fa[N], len[N], pos[N];
void insert(int c)
{
    int cur = ++tot, pre = last; last = cur;
    len[cur] = len[pre]+1; pos[cur] = len[cur];
    while(pre&&!ch[pre][c]) ch[pre][c] = cur, pre = fa[pre];
    if(!pre) return void(fa[cur] = 1);
    int x = ch[pre][c];
    if(len[pre]+1 == len[x]) return (void)(fa[cur] = x);
    int y = ++tot; fa[y] = fa[x]; fa[x] = fa[cur] = y; pos[y] = pos[cur]; len[y] = len[pre]+1;
    memcpy(ch[y], ch[x], sizeof(ch[y]));
    while(pre&&ch[pre][c] == x) ch[pre][c] = y, pre = fa[pre];
}
}

int tot, root[N], val[N<<5], ls[N<<5], rs[N<<5];
void add(int &x, int l, int r, int pos)
{
    if(!x) x = ++tot; ++val[x];
    if(l == r) return;
    int mid = (l+r)>>1;
    if(pos <= mid) add(ls[x], l, mid, pos);
    else add(rs[x], mid+1, r, pos);
}
int merge(int x, int y)
{
    if(!x||!y) return x|y;
    int z = ++tot;
    val[z] = val[x]+val[y];
    ls[z] = merge(ls[x], ls[y]);
    rs[z] = merge(rs[x], rs[y]);
    return z;
}
int query(int x, int l, int r, int ql, int qr)
{
    if(!x||(ql <= l&&r <= qr)) return val[x];
    int mid = (l+r)>>1, ret = 0;
    if(ql <= mid) ret += query(ls[x], l, mid, ql, qr);
    if(qr > mid) ret += query(rs[x], mid+1, r, ql, qr);
    return ret;
}
int tax[N], p[N];
int main()
{ 
    scanf("%d%s%d", &n, s+1, &q);
    reverse(s+1, s+1+n);
    for(int i = 1; i <= n; ++i) sam::insert(s[i]-'0'), add(root[sam::last], 1, n, i);
    for(int i = 1; i <= sam::tot; ++i) ++tax[sam::len[i]];
    for(int i = 1; i <= sam::tot; ++i) tax[i] += tax[i-1];
    for(int i = 1; i <= sam::tot; ++i) p[tax[sam::len[i]]--] = i;
    for(int i = sam::tot; i > 1; --i) 
        sam::pos[sam::fa[p[i]]] = max(sam::pos[sam::fa[p[i]]], sam::pos[p[i]]),
        root[sam::fa[p[i]]] = merge(root[sam::fa[p[i]]], root[p[i]]);
    while(q--)
    {
        scanf("%s", s+1); m = strlen(s+1); reverse(s+1, s+1+m);
        int x = 1, lcs = 0, p = 1; int64 ans = 0;
        for(int i = 1; i <= m; ++i)
        {
            while(x&&!sam::ch[x][s[i]-'0']) x = sam::fa[x], lcs = sam::len[x];
            if(!x) x = 1, lcs = 0;
            else x = sam::ch[x][s[i]-'0'], ++lcs;
            if(lcs == m) break;
        }
        if(lcs == m) p = sam::pos[x]+1, ans += m, x = sam::fa[x];
        else if(x != 1) ans += 1ll*(lcs-sam::len[sam::fa[x]])*query(root[x], 1, n, p, n), x = sam::fa[x];
        while(x != 1) ans += 1ll*(sam::len[x]-sam::len[sam::fa[x]])*query(root[x], 1, n, p, n), x = sam::fa[x];
        ans += query(root[x], 1, n, p, n);
        printf("%lld\n", ans);
    }
    return 0;
}