LibreOJ 2720 「NOI2018」你的名字

发表于 | 分类于 | 17

总算是把这玩意搞懂并做了（
顺便把自己 SAM 构造算法的码风中的变量 whole 改成了 las（

考虑对于 T 中的每一个位置 i 求出 li=max{j∣Ti−j+1…i∈substrings(S)}

（包括 j=0，此时视作空串）
这意味着起点为 i−li+1 及其之后位置的 T1…i 的后缀都是 S 的子串。

首先考虑 l=1,r=|S| 怎么做。
这个要怎么求呢？容易发现 i−li+1 是不降的，证明的话考虑反证，那么可以推出 li 可以更大并与 max 矛盾。
设 len 表示当前的 li，p 表示 Ti−len+1…i 在 S 的后缀自动机上对应的状态。
那么如何从 i−1 转移到 li 呢？首先检查 p 是否有 Ti 的转移，如果有直接转移即可。
否则，一直令 len 自减，同时维护 p（即当 len 已经不属于 p 所包含的长度时将 p 跳至其父亲），直到 p 有 Ti 的转移。
（实际上，若 l=1,r=|S|，不需要自减，直接跳到父亲即可，因为自减在这一情况下并不会对转移造成任何改变。）

那么，对于一般情况（l≠1,r≠|S|），则我们要思考 Sl…r 的后缀自动机和 S 的后缀自动机有什么不同。
注意到 Parent Tree 是不会受影响的，所以只需要考虑如果检查 p 有 Ti 的转移。
若 p 在 S 上有 Ti 的转移，设转移到状态 q，那么便是需要知道 endpos(q)∩[l+len,r] 是否为空。
这个可以线段树合并解决。

但是求出这个之后，还需要去重。
考虑对 T 建后缀自动机，利用后缀自动机来去重。
对于状态 p，其贡献应为 max(0,len(p)−max(len(fa(p)),lr(p)))，其中 r(p)=maxendpos(p)。
这个想必还是比较显然的，意即从这个状态包含的所有串中去掉 Sl…r 的子串。

代码： 

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6;
int n,m,q;
char s[N + 5],t[N + 5];
namespace SEG
{
    struct node
    {
        int ls,rs;
    } seg[(N << 5) + 10];
    int seg_tot,rt[N + 5];
    void insert(int x,int &p,int tl,int tr)
    {
        int &tot = seg_tot;
        !p && (p = ++tot);
        if(tl == tr)
            return ;
        int mid = tl + tr >> 1;
        x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
    }
    int merge(int x,int y)
    {
        if(!x || !y)
            return x | y;
        int &tot = seg_tot;
        int p = ++tot;
        seg[p].ls = merge(seg[x].ls,seg[y].ls),seg[p].rs = merge(seg[x].rs,seg[y].rs);
        return p;
    }
    int query(int l,int r,int p,int tl,int tr)
    {
        if(!p)
            return 0;
        if(l <= tl && tr <= r)
            return 1;
        int mid = tl + tr >> 1;
        if(l <= mid && query(l,r,seg[p].ls,tl,mid))
            return 1;
        if(r > mid && query(l,r,seg[p].rs,mid + 1,tr))
            return 1;
        return 0;
    }
}
namespace SAM
{
    struct node
    {
        int ch[26];
        int fa,len,suf,rt;
    } sam[N + 5];
    int las = 1,tot = 1;
    int c[N + 5],a[N + 5];
    inline void insert(int x)
    {
        int cur = las,p = ++tot;
        sam[p].len = sam[cur].len + 1,sam[p].suf = 1;
        for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                int nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt,sam[nxt].suf = 0;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        las = p;
    }
    inline void build()
    {
        for(register int i = 1;i <= n;++i)
            insert(s[i] - 'a');
        for(register int i = 1;i <= tot;++i)
            ++c[sam[i].len];
        for(register int i = 1;i <= n;++i)
            c[i] += c[i - 1];
        for(register int i = tot;i > 1;--i)
            a[c[sam[i].len]--] = i;
        for(register int i = tot;i > 1;--i)
            sam[a[i]].suf && (SEG::insert(sam[a[i]].len,sam[a[i]].rt,1,n),1),sam[sam[a[i]].fa].rt = SEG::merge(sam[sam[a[i]].fa].rt,sam[a[i]].rt);
    }
}
namespace Sam
{
    struct node
    {
        int ch[26];
        int fa,len,r;
    } sam[(N << 1) + 5];
    int las,tot;
    int l[(N << 1) + 5];
    int L,R;
    inline void init()
    {
        memset(sam + 1,0,(sizeof sam[0]) * tot),las = tot = 1;
    }
    inline void insert(int x)
    {
        int cur = las,p = ++tot;
        sam[p].r = sam[p].len = sam[cur].len + 1;
        for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                int nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        las = p;
    }
    inline void build()
    {
        for(register int i = 1,x,len = 0,p = 1;i <= m;++i)
        {
            insert(x = t[i] - 'a');
            for(;;)
            {
                if(SAM::sam[p].ch[x] && SEG::query(L + len,R,SAM::sam[SAM::sam[p].ch[x]].rt,1,n))
                {
                    p = SAM::sam[p].ch[x],++len;
                    break;
                }
                if(!len)
                    break;
                if(--len == SAM::sam[SAM::sam[p].fa].len)
                    p = SAM::sam[p].fa;
            }
            l[i] = len;
        }
    }
    inline long long calc()
    {
        long long ret = 0;
        for(register int i = 2;i <= tot;++i)
            ret += max(0,sam[i].len - max(sam[sam[i].fa].len,l[sam[i].r]));
        return ret;
    }
}
int main()
{
    freopen("name.in","r",stdin),freopen("name.out","w",stdout);
    scanf("%s%d",s + 1,&q),n = strlen(s + 1);
    SAM::build();
    for(;q;--q)
    {
        Sam::init(),scanf("%s%d%d",t + 1,&Sam::L,&Sam::R),m = strlen(t + 1);
        Sam::build(),printf("%lld\n",Sam::calc());
    }
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment