Codeforces 666E Forensic Examination

发表于 | 分类于 | 8

请问我是怎么忘记在构造 SAM 复制结点的时候忘记清空别的东西，还把倍增循环顺序打反的……
这道题告诉我，请不要怀疑你的广义 SAM 模板（本来以为是这个出锅了

首先对 \(T_{1\dots m}\) 建广义后缀自动机，然后对 \(S\) 中的每个位置 \(i\) 求出 \(S_{1\dots i}\) 最长的为 \(T_{1\dots m}\) 中子串的后缀，这个是后缀自动机基本操作。
即，记录当前后缀在后缀自动机上对应的状态，当新增字符时查看是否有对应转移，如果有直接转移并更新长度，如果没有则跳 Parent Tree 直到有转移。
记这个后缀的长度为 \(l_i\)，并同时记录这个后缀在后缀自动机上对应的状态 \({\rm ed}_i\)。

询问时，考虑 \({\rm ed}_{p_r}\)，倍增在其祖先（即后缀）中找到一个最浅（即 \(\rm len\) 最小）的状态 \(u\)，则包含 \(S_{p_l\dots p_r}\) 的状态恰为 \(u\) 子树内所有状态。
那么如何求答案？考虑以 \(1\dots m\) 为下标在后缀自动机上维护线段树，表示这个状态在 \(T_{1\dots m}\) 中某个串中的出现次数，然后维护众数，线段树合并即可。
（广义后缀自动机套雨天的尾巴（雾

然而注意特判几个不存在的情况。

代码： 

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e5;
const int LG = 18;
int n,m,q;
char s[N + 5],t[N + 5];
int ed[N + 5],l[N + 5];
namespace SEG
{
    struct val
    {
        int pos,v;
        inline val()
        {
            pos = v = 0;
        }
        inline bool operator<(const val &o) const
        {
            return v == o.v ? pos > o.pos : v < o.v;
        }
    };
    struct node
    {
        val v;
        int ls,rs;
    } seg[(N << 5) + 10];
    int seg_tot;
    void insert(int x,int &p,int tl,int tr)
    {
        int &tot = seg_tot;
        !p && (p = ++tot);
        if(tl == tr)
        {
            ++seg[p].v.v,seg[p].v.pos = tl;
            return ;
        }
        int mid = tl + tr >> 1;
        x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
        seg[p].v = max(seg[seg[p].ls].v,seg[seg[p].rs].v);
    }
    int merge(int x,int y,int tl,int tr)
    {
        if(!x || !y)
            return x | y;
        int &tot = seg_tot;
        int p = ++tot;
        if(tl == tr)
        {
            seg[p].v.v = seg[x].v.v + seg[y].v.v,seg[p].v.pos = tl;
            return p;
        }
        int mid = tl + tr >> 1;
        seg[p].ls = merge(seg[x].ls,seg[y].ls,tl,mid);
        seg[p].rs = merge(seg[x].rs,seg[y].rs,mid + 1,tr);
        seg[p].v = max(seg[seg[p].ls].v,seg[seg[p].rs].v);
        return p;
    }
    val query(int l,int r,int p,int tl,int tr)
    {
        if(!p || (l <= tl && tr <= r))
            return seg[p].v;
        int mid = tl + tr >> 1;
        val ret;
        l <= mid && (ret = max(ret,query(l,r,seg[p].ls,tl,mid)),1);
        r > mid && (ret = max(ret,query(l,r,seg[p].rs,mid + 1,tr)),1);
        return ret;
    }
}
namespace SAM
{
    struct node
    {
        int ch[26];
        int fa,len,rt;
    } sam[(N << 1) + 5];
    int tot = 1,las = 1;
    int f[(N << 1) + 5][LG + 5];
    inline void insert(int x,int pos)
    {
        if(sam[las].ch[x] && sam[las].len + 1 == sam[sam[las].ch[x]].len)
        {
            SEG::insert(pos,sam[las = sam[las].ch[x]].rt,1,m);
            return ;
        }
        int cur = las,p = ++tot,flag = 0,nxt;
        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
            {
                cur == las && (flag = 1),nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt,sam[nxt].rt = 0;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        SEG::insert(pos,sam[las = flag ? nxt : p].rt,1,m);
    }
    int c[N + 5],a[(N << 1) + 5];
    inline void init()
    {
        for(register int i = 1;i <= tot;++i)
            ++c[sam[i].len],f[i][0] = sam[i].fa;
        for(register int i = 1;i <= LG;++i)
            for(register int j = 1;j <= tot;++j)
                f[j][i] = f[f[j][i - 1]][i - 1];
        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[sam[a[i]].fa].rt = SEG::merge(sam[sam[a[i]].fa].rt,sam[a[i]].rt,1,m);
    }
}
SEG::val ans;
int main()
{
    scanf("%s%d",s + 1,&m),n = strlen(s + 1);
    for(register int i = 1;i <= m;++i)
    {
        scanf("%s",t + 1),SAM::las = 1;
        for(char *p =  t + 1;*p;SAM::insert(*p++ - 'a',i));
    }
    SAM::init();
    for(register int i = 1,x,len = 0,p = 1;i <= n;++i)
    {
        x = s[i] - 'a';
        if(SAM::sam[p].ch[x])
            p = SAM::sam[p].ch[x],++len;
        else
        {
            for(;p && !SAM::sam[p].ch[x];p = SAM::sam[p].fa);
            !p ? (p = 1,len = 0) : (len = SAM::sam[p].len + 1,p = SAM::sam[p].ch[x]);
        }
        ed[i] = p,l[i] = len;
    }
    scanf("%d",&q);
    for(int L,R,pl,pr;q;--q)
    {
        scanf("%d%d%d%d",&L,&R,&pl,&pr);
        if(pr - pl + 1 > l[pr])
            printf("%d 0\n",L);
        else
        {
            int p = ed[pr];
            for(register int i = LG;~i;--i)
                SAM::sam[SAM::f[p][i]].len >= pr - pl + 1 && (p = SAM::f[p][i]);
            ans = SEG::query(L,R,SAM::sam[p].rt,1,m),!ans.v && (ans.pos = L);
            printf("%d %d\n",ans.pos,ans.v);
        }
    }
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment