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
|
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
const int MAXN = 1e5 + 10;
using namespace std;
typedef long long ll;
struct
{
int x;
poi *nt;
} *a[MAXN];
int i, n, len, l, r, s, ans, p[MAXN], dep[MAXN], fa[MAXN][30];
char st[MAXN];
inline void link(const int &x, const int &y)
{
poi *p = new poi;
p->x = y;
p->nt = a[x];
a[x] = p;
}
inline void dfs(const int &x)
{
poi *p = new poi;
for (p = a[x]; p; p = p->nt)
if (p->x != fa[x][0])
{
dep[p->x] = dep[x] + 1;
fa[p->x][0] = x;
dfs(p->x);
}
}
inline void pre()
{
p[1] = 0;
len = strlen(st + 1);
register int j = 0;
for (register int i = 2; i <= len; ++i)
{
while (j && st[i] != st[j + 1]) j = p[j];
if (st[i] == st[j + 1]) j++;
p[i] = j;
}
for (register int i = 1; i <= len; ++i) link(i, p[i]), link(p[i], i);
dfs(0);
for (j = 1; j <= 26; ++j)
for (register int i = 1; i <= len; ++i)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
return;
}
inline int getlca(int x, int y)
{
if (dep[y] > dep[x]) swap(x, y);
register int d = dep[x] - dep[y];
for (register int i = 0; i <= 26; ++i)
if (d & (1 << i))
x = fa[x][i];
if (x == y) return x;
for (register int i = 26; i >= 0; i--)
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
inline void _read(int &x)
{
x = 0;
char t = getchar();
while (!isdigit(t)) t = getchar();
while (isdigit(t))
{
x = x * 10 + t - '0';
t = getchar();
}
}
int main()
{
gets(st + 1);
pre();
_read(n);
for (register int i = 1; i <= n; ++i)
{
_read(l), _read(r);
register int lca = getlca(l, r);
printf("%d %d", dep[lca], lca);putchar('n');
}
return 0;
}
|
近期评论