洛谷 5576 「CmdOI2019」口头禅

发表于 | 分类于 | 9

首先考虑如何用 SAM 求多串 LCP。
考虑选取一个基准串，对其他串建 SAM 并把基准串分别放到上面匹配，同位置的匹配长度的最小值的最大值即为答案。
当然，对基准串建 SAM 并把别的串匹配并打标记也是可以的。

若基准串为 sx，则复杂度为 O(|sx|n+∑|si|)。

对于此题，考虑用类似猫树的方式进行分治并计算答案。
出题人给出了一种十分玄妙的分治方法：倍增处理。
设一个阈值 lim，分治时将区间内长度不超过 2lim 的串拿出来，取中点作为基准串。
若一个区间内不存在长度不超过 2lim 的字符串，令 lim 加一。

则分治部分的复杂度为 O(nlog2n)（视 n,∑|si| 同阶）。

统计答案的部分复杂度看起来不大对。
但是有结论：若将询问记忆化，复杂度为 O(n√m)。

证明：
首先容易发现对于当前分治区间，2lim 是 O(1n∑|si|) 级别的（考虑 2lim 与最短串长度的关系）。
分类讨论。
若某个区间的最短串长度不超过 m−1/2∑|si|，复杂度共为 O(n√m)。
若某个区间的最短串长度超过 m−1/2∑|si|，这个区间对应的询问最多有 O(m) 种，复杂度同样为 O(n√m)。
（视 n,∑|si| 同阶）

总复杂度大概是 O(n(log2n+√m))。
（我不知道为什么要开 O2 才能过 /kel）

代码： 

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tr1/unordered_map>
using namespace std;
const int N = 2e4;
const int M = 1e5;
const int L = 4e5;
int n,m;
char S[L + 5],*s[N + 5];
int len[N + 5];
int rt[N + 5];
int ans[M + 5];
struct s_query
{
    int l,r,id;
} qry[M + 5];
tr1::unordered_map< int,tr1::unordered_map<int,int> > mem;
namespace SAM
{
    struct node
    {
        int ch[2];
        int fa,len;
    } sam[(L << 1) + 5];
    int las,tot;
    inline void insert(int x,int rt)
    {
        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 = rt;
        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;
    }
}
int sLen[(L << 1) + 5],*Len[N + 5];
void solve(int l,int r,int L,int R,int lim)
{
    if(L > R)
        return ;
    static int t[N + 5];
    int tot = 0;
    for(;;lim <<= 1)
    {
        for(register int i = l;i <= r;++i)
            len[i] <= lim && (t[++tot] = i);
        if(tot)
            break;
    }
    int mid = t[tot + 1 >> 1];
    Len[l] = sLen;
    for(register int i = l + 1;i <= r;++i)
        Len[i] = Len[i - 1] + len[mid];
    for(register int i = 1;i <= len[mid];++i)
        Len[mid][i] = i;
    for(register int i = mid - 1;i >= l;--i)
        for(register int j = 1,x,p = rt[i],cur = 0;j <= len[mid];++j)
        {
            x = s[mid][j] ^ '0';
            if(SAM::sam[p].ch[x])
                ++cur,p = SAM::sam[p].ch[x];
            else
            {
                for(;p && !SAM::sam[p].ch[x];p = SAM::sam[p].fa);
                !p ? (p = rt[i],cur = 0) : (cur = SAM::sam[p].len + 1,p = SAM::sam[p].ch[x]);
            }
            Len[i][j] = min(Len[i + 1][j],cur);
        }
    for(register int i = mid + 1;i <= r;++i)
        for(register int j = 1,x,p = rt[i],cur = 0;j <= len[mid];++j)
        {
            x = s[mid][j] ^ '0';
            if(SAM::sam[p].ch[x])
                ++cur,p = SAM::sam[p].ch[x];
            else
            {
                for(;p && !SAM::sam[p].ch[x];p = SAM::sam[p].fa);
                !p ? (p = rt[i],cur = 0) : (cur = SAM::sam[p].len + 1,p = SAM::sam[p].ch[x]);
            }
            Len[i][j] = min(Len[i - 1][j],cur);
        }
    static s_query q_t[2][M + 5];
    int q_tot[2];
    q_tot[0] = q_tot[1] = 0;
    for(register int i = L;i <= R;++i)
        if(mid >= qry[i].l && mid <= qry[i].r)
        {
            if(mem.count(qry[i].l) && mem[qry[i].r].count(qry[i].r))
                ans[qry[i].id] = mem[qry[i].l][qry[i].r];
            else
            {
                for(register int j = 1;j <= len[mid];++j)
                    ans[qry[i].id] = max(ans[qry[i].id],min(Len[qry[i].l][j],Len[qry[i].r][j]));
                mem[qry[i].l][qry[i].r] = ans[qry[i].id];
            }
        }
        else if(mid > qry[i].r)
            q_t[0][++q_tot[0]] = qry[i];
        else
            q_t[1][++q_tot[1]] = qry[i];
    for(register int i = 1;i <= q_tot[0];++i)
        qry[L + i - 1] = q_t[0][i];
    for(register int i = 1;i <= q_tot[1];++i)
        qry[L + q_tot[0] + i - 1] = q_t[1][i];
    solve(l,mid - 1,L,L + q_tot[0] - 1,lim),solve(mid + 1,r,L + q_tot[0],L + q_tot[0] + q_tot[1] - 1,lim);
}
int main()
{
    scanf("%d%d",&n,&m),s[1] = S;
    for(register int i = 1;i <= n;++i)
    {
        scanf("%s",s[i] + 1),len[i] = strlen(s[i] + 1),rt[i] = SAM::las = ++SAM::tot;
        for(register int j = 1;j <= len[i];++j)
            SAM::insert(s[i][j] ^ '0',rt[i]);
        s[i + 1] = s[i] + len[i];
    }
    for(register int i = 1;i <= m;++i)
        scanf("%d%d",&qry[i].l,&qry[i].r),qry[i].id = i;
    solve(1,n,1,m,1);
    for(register int i = 1;i <= m;++i)
        printf("%d\n",ans[i]);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment