口胡 LOJ2059 [TJOI & HEOI2016 字符串]

传送门

题目大意

给定一个长度为$n\le100000$的字符串S,$m\le100000$次询问$S[a:b]$的所有子串和$S[c:d]$的所有字串中的最长的LCP的长度。

解析

考虑二分答案$L$。

则问题变为有多少个起始位置在$[a, b − L + 1]$之间$i$,满足$L\le LCP(S[i : n], S[c : n])$。

这个把后缀数组搞出来,然后和某个后缀的$LCP ≥ L$的范围是一段区间,可以$ST$表。

接下来的问题变为在后缀数组的某个区间$[l, r]$中,是否存在一个介于$[a, b − L + 1]$之间的数字。线段树合并就可以了。

Code

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
#define  REP(i, s, e) for (int i = s; i <= e; i++)
#define DREP(i, s, e) for (int i = s; i >= e; i--)
#define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
const int maxn = 200000 + 10, maxN = maxn << 1;

int ls[maxn*50], rs[maxn*50], cur;
#define mid (l + r >> 1)
#define lson ls[p], l, mid
#define rson rs[p], mid + 1, r

void build(int &p, int l, int r, int pos)
{
p = ++cur;
if (l == r) return;
else
if (pos <= mid) build(lson, pos);
else build(rson, pos);
}

int merge(int a, int b)
{
if (!a || !b) return a + b;
int now = ++cur;
ls[now] = merge(ls[a], ls[b]);
rs[now] = merge(rs[a], rs[b]);
return now;
}

bool query(int p, int l, int r, int L, int R)
{
if (!p) return 0;
if (L == l && r == R) return 1;
else
{
if (R <= mid) return query(lson, L, R);
if (L > mid) return query(rson, L, R);
return query(lson, L, mid) || query(rson, mid+1, R);
}
}

int n, m;
char str[maxN];
int ch[maxN][26], ne[maxN][21], Max[maxN], sam_cur = 1, start = 1, last = 1;
int rt[maxN], fin[maxN];

inline int newnode(int _Max) {return Max[++sam_cur] = _Max, sam_cur;}
inline void extend(int c, int id)
{
int v = last, u = newnode(Max[v] + 1);
build(rt[u], 1, n, id);
for (; v && !ch[v][c]; v = ne[v][0]) ch[v][c] = u;
if (!v) ne[u][0] = start;
else if (Max[v] + 1 == Max[ch[v][c]]) ne[u][0] = ch[v][c];
else
{
int New = newnode(Max[v] + 1), Old = ch[v][c];
copy(ch[Old], ch[Old] + 26, ch[New]);
ne[New][0] = ne[Old][0];
ne[u][0] = ne[Old][0] = New;
for (; v && ch[v][c] == Old;v = ne[v][0]) ch[v][c] = New;
}
fin[id] = last = u;
}

int bg[maxN], nex[maxN], to[maxN], e;
inline void add(int x, int y)
{
e++;
to[e] = y;
nex[e] = bg[x];
bg[x] = e;
}
void dfs(int x)
{
for (int i = bg[x]; i ; i = nex[i])
{
dfs(to[i]);
rt[x] = merge(rt[x], rt[to[i]]);
}
}

inline bool judge(int pos, int Mid, int a, int b)
{
DREP(i, 19, 0)
if (Max[ne[pos][i]] >= Mid) pos = ne[pos][i];
return query(rt[pos], 1, n, a+Mid-1, b);
}

int main()
{
#ifdef CraZYali
freopen("2059.in", "r", stdin);
freopen("2059.out", "w", stdout);
#endif
scanf("%d%d\n%s", &n, &m, str + 1);
reverse(str+1, str+n+1);
REP(i, 1, n) extend(str[i]-'a', i);
REP(j, 1, 19)
REP(i, 1, sam_cur)
ne[i][j] = ne[ne[i][j-1]][j-1];
REP(i, 2, sam_cur) add(ne[i][0], i);
dfs(start);
while (m--)
{
int a, b, c, d;
scanf("%d%d%d%d", &b, &a, &d, &c);
a = n-a+1, b = n-b+1, c = n-c+1, d = n-d+1;
int pos = fin[d];
int l(1), r(min(b-a+1, d-c+1));
while (l <= r)
if (judge(pos, mid, a, b)) l = mid + 1;
else r = mid - 1;
printf("%d\n", l-1);
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×