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
| #include <cstdio>
#include <algorithm>
#include <cctype>
#include <vector>
#include <cstring>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = 0)
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 1e6+5;
struct Edge
{
int next, to;
Edge(int next = 0, int to = 0):next(next), to(to) {};
}edge[N];
int tot, head[N];
void add(int x, int y) { edge[++tot] = Edge(head[x], y); head[x] = tot; }
namespace sam
{
int last = 1, tot = 1, ch[N][26], fa[N], len[N], pos[N];
void insert(int c)
{
int cur = ++tot, pre = last; last = cur;
len[cur] = len[pre]+1; pos[len[cur]] = cur;
while(pre&&!ch[pre][c]) ch[pre][c] = cur, pre = fa[pre];
if(!pre) return void(fa[cur] = 1);
int x = ch[pre][c];
if(len[pre]+1 == len[x]) return void(fa[cur] = x);
int y = ++tot; fa[y] = fa[x]; len[y] = len[pre]+1; fa[x] = fa[cur] = y;
memcpy(ch[y], ch[x], sizeof(ch[x]));
while(pre&&ch[pre][c] == x) ch[pre][c] = y, pre = fa[pre];
}
}
int n, m, q;
char s[N];
int d[N], dfn[N], t, son[N], top[N], size[N], pos[N];
void dfs(int x)
{
dfn[x] = ++t; d[x] = d[sam::fa[x]]+1; size[x] = 1;
for(int i = head[x]; i; i = edge[i].next)
{
int y = edge[i].to; dfs(y);
size[x] += size[y]; son[x] = size[son[x]]>size[y]?son[x]:y;
}
}
void dfs(int x, int topf)
{
top[x] = topf;
if(son[x]) dfs(son[x], topf);
for(int i = head[x]; i; i = edge[i].next)
{
int y = edge[i].to;
if(y^son[x]) dfs(y, y);
}
}
int LCA(int x, int y)
{
while(top[x] != top[y])
{
if(d[top[x]] < d[top[y]]) swap(x, y);
x = sam::fa[top[x]];
}
return d[x]<d[y]?x:y;
}
int p[N];
bool cmp(int x, int y) { return dfn[x] < dfn[y]; }
namespace vtree
{
int top, s[N], col[N], f[N];
vector<int> edge[N];
void add(int x, int y) { edge[x].push_back(y); }
void insert(int x)
{
int lca = LCA(x, s[top]);
if(s[top] == lca) return void(s[++top] = x);
while(top > 1&&dfn[s[top-1]] >= dfn[lca]) add(s[top-1], s[top]), --top;
if(s[top] != lca) add(lca, s[top]), s[top] = lca;
s[++top] = x;
}
void build()
{
s[top = 1] = 1;
for(int i = 1; i <= m; ++i) insert(p[i]), col[p[i]] = 1;
while(top > 1) add(s[top-1], s[top]), --top;
}
int64 dp(int x)
{
int64 ret = 0; f[x] = col[x]; col[x] = 0;
for(int i = 0; i < edge[x].size(); ++i)
{
int y = edge[x][i]; ret += dp(y);
ret += 1ll*f[x]*f[y]*sam::len[x];
f[x] += f[y];
}
edge[x].clear();
return ret;
}
}
int main()
{
n = read(), q = read(); scanf("%s", s+1); reverse(s+1, s+1+n);
for(int i = 1; i <= n; ++i) sam::insert(s[i]-'a');
for(int x = 2; x <= sam::tot; ++x) add(sam::fa[x], x);
dfs(1); dfs(1, 1);
while(q--)
{
m = read();
for(int i = 1; i <= m; ++i) p[i] = sam::pos[n-read()+1];
sort(p+1, p+1+m); m = unique(p+1, p+1+m)-p-1;
sort(p+1, p+1+m, cmp); vtree::build();
printf("%lld\n", vtree::dp(1));
}
return 0;
}
|