首先讲题解做法，也是我第一个想到的做法。
对 \(m_{1\dots N}\) 建 AC 自动机，将询问串放在其上匹配，最后走到的状态和其 Fail 树上的全部祖先便是对这个询问串有贡献的。
然后还有一个树上路径的限制，考虑在 Fail 树上用主席树按照树剖的 DFS 序维护每个状态到根路径上的贡献。
然后讲一个假在线做法。
注意到询问串并没有加密，考虑对询问串建广义 SAM，把 \(m_{1\dots N}\) 放在其上匹配，最后走到的状态和其 Parent Tree 上的子树内的状态便是每个模式串贡献到的询问串。
同样建到根路径上的主席树，但是要对询问串的每一个前缀统计贡献。
然后讲一个小常数简单做法，也就是我写的做法。
考虑枚举询问串中匹配的起始位置，枚举匹配长度，在原树上建可持久化 Trie 维护每个结点到根路径上的字符串，通过差分得到一段树上路径的 Trie，如此匹配。
前两个做法都是 \(O(\sum |w| \log^2 n)\) 的，最后一个是 \(O(\max |m_i| \sum |w|)\) 的。
代码： 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
using namespace std;
const int N = 1e5;
const int M = 1e6;
const int L = 10;
int n,m,online,q;
char a[N + 5][L + 5],s[N + 5];
int len[N + 5],ans;
namespace TRIE
{
struct node
{
int ch[26];
int sum,ed;
} trie[M + 5];
void insert(char *s,int len,int &rt)
{
static int tot = 0;
trie[++tot] = trie[rt],++trie[rt = tot].sum;
int p = rt;
for(register int i = 1;i <= len;++i)
trie[++tot] = trie[trie[p].ch[s[i] - 'a']],++trie[p = trie[p].ch[s[i] - 'a'] = tot].sum;
++trie[p].ed;
}
int query(char *s,int len,int p,int q,int x,int y)
{
if(!(trie[p].sum + trie[q].sum - trie[x].sum - trie[y].sum))
return 0;
int ret = 0;
for(register int i = 1;i <= len;++i)
{
p = trie[p].ch[s[i] - 'a'],q = trie[q].ch[s[i] - 'a'],x = trie[x].ch[s[i] - 'a'],y = trie[y].ch[s[i] - 'a'];
if(!(trie[p].sum + trie[q].sum - trie[x].sum - trie[y].sum))
break;
if(trie[p].ed + trie[q].ed - trie[x].ed - trie[y].ed)
ret = max(ret,i);
}
return ret;
}
}
namespace HLD
{
int to[N + 5],pre[N + 5],first[N + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5];
int rt[N + 5];
int q[N + 5],head,tail;
void bfs()
{
dep[q[++tail] = 1] = 1;
for(register int p;head < tail;)
{
sz[p = q[++head]] = 1,TRIE::insert(a[p],len[p],rt[p] = rt[fa[p]]);
for(register int i = first[p];i;i = pre[i])
dep[to[i]] = dep[p] + 1,q[++tail] = to[i];
}
for(register int i = n;i > 1;--i)
{
sz[fa[q[i]]] += sz[q[i]];
if(!son[fa[q[i]]] || sz[q[i]] > sz[fa[q[i]]])
son[fa[q[i]]] = q[i];
}
for(register int i = 1;i <= n;++i)
top[q[i]] = q[i] == son[fa[q[i]]] ? top[fa[q[i]]] : q[i];
}
int getlca(int x,int y)
{
while(top[x] ^ top[y])
dep[top[x]] > dep[top[y]] ? (x = fa[top[x]]) : (y = fa[top[y]]);
return dep[x] < dep[y] ? x : y;
}
}
int main()
{
scanf("%d%d",&n,&online);
for(register int i = 1;i <= n;++i)
scanf("%s",a[i] + 1),len[i] = strlen(a[i] + 1);
for(register int i = 2;i <= n;++i)
scanf("%d",HLD::fa + i),HLD::add(HLD::fa[i],i);
HLD::bfs();
scanf("%d",&q);
for(int x,y,lca;q;--q)
{
scanf("%d%d%s",&x,&y,s + 1),online && (x ^= ans,y ^= ans),ans = 0,m = strlen(s + 1);
lca = HLD::getlca(x,y);
for(register int i = 1;i <= m;++i)
ans = max(ans,TRIE::query(s + i - 1,min(L,m - i + 1),HLD::rt[x],HLD::rt[y],HLD::rt[lca],HLD::rt[HLD::fa[lca]]));
printf("%d\n",ans);
}
}