LibreOJ 6031 「雅礼集训 2017 Day1」字符串

发表于 | 分类于 | 20

小清新根号分治（

注意到 ∑|w|=kq≤105，考虑设一个阈值 S（以下视 n,m,kq 同阶）。
若 k≤S，则暴力枚举 w 串的每个子串，在 SAM 上求出出现次数，然后算出这个子串在 [a,b] 内的贡献，复杂度 O(qk2)=O(nS)。
若 k>S，则对 w 串的每个前缀在 SAM 上匹配，然后枚举 [a,b] 内的一个区间，在 Parent Tree 上倍增找其在 SAM 上的对应状态。复杂度 O(qk+qmlogn)=O(n2Slogn)。

显然当 S 取 O(√nlogn) 时两部分复杂度均衡为 O(n√nlogn)。

代码： 

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
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int LG = 17;
const int S = 1400;
int n,m,q,k;
char s[N + 5],w[N + 5];
int l[N + 5],ed[N + 5];
struct s_query
{
    int l,r;
} qry[N + 5];
namespace SAM
{
    struct node
    {
        int ch[26];
        int fa,len,sz;
    } sam[(N << 1) + 5];
    int las = 1,tot = 1;
    int c[N + 5],a[(N << 1) + 5];
    int f[LG + 5][(N << 1) + 5];
    inline void insert(int x)
    {
        int cur = las,p = ++tot;
        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,sam[nxt].sz = 0;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        ++sam[las = p].sz;
    }
    inline void build()
    {
        for(register int i = 1;i <= tot;++i)
            ++c[sam[i].len],f[0][i] = sam[i].fa;
        for(register int i = 1;i <= LG;++i)
            for(register int j = 1;j <= tot;++j)
                f[i][j] = f[i - 1][f[i - 1][j]];
        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].sz += sam[a[i]].sz;
    }
}
long long ans;
vector<int> vec[S + 5][S + 5];
int main()
{
    scanf("%d%d%d%d%s",&n,&m,&q,&k,s + 1);
    for(register int i = 1;i <= n;++i)
        SAM::insert(s[i] - 'a');
    SAM::build();
    for(register int i = 1;i <= m;++i)
        scanf("%d%d",&qry[i].l,&qry[i].r),++qry[i].l,++qry[i].r;
    if(k <= S)
    {
        for(register int i = 1;i <= m;++i)
            vec[qry[i].l][qry[i].r].push_back(i);
        for(int a,b;q;--q)
        {
            scanf("%s%d%d",w + 1,&a,&b),++a,++b,ans = 0;
            for(register int i = 1;i <= k;++i)
                for(register int j = i,p = 1;j <= k && SAM::sam[p].ch[w[j] - 'a'];++j)
                    p = SAM::sam[p].ch[w[j] - 'a'],
                    ans += (long long)SAM::sam[p].sz * (upper_bound(vec[i][j].begin(),vec[i][j].end(),b) - lower_bound(vec[i][j].begin(),vec[i][j].end(),a));
            printf("%lld\n",ans);
        }
        return 0;
    }
    for(int a,b;q;--q)
    {
        scanf("%s%d%d",w + 1,&a,&b),++a,++b,ans = 0;
        for(register int i = 1,p = 1,len = 0,x;i <= k;++i)
        {
            x = w[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]);
            }
            l[i] = len,ed[i] = p;
        }
        for(register int i = a,p,len;i <= b;++i)
        {
            p = ed[qry[i].r],len = l[qry[i].r];
            if(len < qry[i].r - qry[i].l + 1)
                continue;
            for(register int j = LG;~j;--j)
                if(SAM::sam[SAM::f[j][p]].len >= qry[i].r - qry[i].l + 1)
                    p = SAM::f[j][p];
            ans += SAM::sam[p].sz;
        }
        printf("%lld\n",ans);
    }
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment