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
| #include <bits/stdc++.h>
using namespace std;
const int SIGMA = 27;
const int MAXN = 2e5 + 5;
int n, k;
int f[MAXN << 1], s[MAXN << 1];
struct SAM {
struct Node {
int len, link;
int trans[SIGMA];
} node[MAXN << 1];
#define len(u) node[u].len
#define link(u) node[u].link
#define trans(u, c) node[u].trans[c]
int cnt, last;
void init() {
len(0) = 0;
link(0) = -1;
cnt = 0;
last = 0;
for (int i = 0; i < SIGMA; ++i)
trans(0, i) = 0;
}
void insert(int c) {
int cur = ++cnt;
for (int i = 0; i < SIGMA; ++i)
trans(cur, i) = 0;
len(cur) = len(last) + 1;
int p = last;
while (p != -1 && trans(p, c) == 0) {
trans(p, c) = cur;
p = link(p);
}
if (p == -1) {
link(cur) = 0;
} else {
int q = trans(p, c);
if (len(p) + 1 == len(q)) {
link(cur) = q;
} else {
int clone = ++cnt;
for (int i = 0; i < SIGMA; ++i)
trans(clone, i) = 0;
len(clone) = len(p) + 1;
for (int i = 0; i < SIGMA; ++i)
trans(clone, i) = trans(q, i);
link(clone) = link(q);
while (p != -1 && trans(p, c) == q) {
trans(p, c) = clone;
p = link(p);
}
link(q) = link(cur) = clone;
}
}
f[cur] = 1;
last = cur;
}
} T;
struct Edge {
int v, nxt;
} edge[MAXN << 1];
int head[MAXN << 1], cnt;
void AddEdge(int u, int v) {
edge[++cnt].v = v;
edge[cnt].nxt = head[u];
head[u] = cnt;
}
void dfs(int u) {
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].v;
dfs(v);
f[u] += f[v];
}
if (u == 0) return;
if (f[u] == k) {
int l = T.node[T.node[u].link].len + 1;
int r = T.node[u].len;
s[l] += 1;
s[r + 1] -= 1;
}
}
int t;
char str[MAXN];
int main() {
scanf("%d", &t);
while (t--) {
T.init();
scanf("%s", str + 1);
n = strlen(str + 1);
scanf("%d", &k);
for (int i = 1; i <= n; ++i)
T.insert(str[i] - 'a');
for (int i = 1; i <= T.cnt; ++i) {
AddEdge(T.node[i].link, i);
}
dfs(0);
int ans = -1, ans_val = 0;
for (int i = 1; i <= n; ++i) {
s[i] += s[i - 1];
if (s[i] && s[i] >= ans_val)
ans = i, ans_val = s[i];
}
printf("%d\n", ans);
for (int i = 0; i <= T.cnt; ++i) {
f[i] = 0;
head[i] = 0;
s[i] = 0;
}
cnt = 0;
}
return 0;
}
|