依然是一个广义 SAM 屑题（
于是 ACAM 照样能做（
为了符合各种字符串数据结构的习惯，考虑将所有串反过来。
发现将输入看做 Trie 上的连边就可以了。
于是直接 BFS 建广义 SAM，询问则将询问串反过来放在广义 SAM 上跑，达到的状态的 Parent Tree 上子树内所有状态都是以它为一个后缀的字符串。
又因为每个状态一定都是一个名字，所以直接对所有串维护 \(|{\rm endpos}|\) 即可。
代码： 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
using namespace std;
const int N = 1e6;
int n,m,k;
char s[N + 5];
struct node
{
int ch[26];
int ed;
} tr[N + 5];
namespace SAM
{
struct node
{
int ch[26];
int fa,len;
} sam[(N << 1) + 5];
int tot = 1,las = 1,sz[(N << 1) + 5];
inline void insert(int x)
{
int cur = las,p = las = ++tot,nxt;
sam[p].len = sam[cur].len + 1,sz[p] = 1;
for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
sam[cur].ch[x] = p;
if(!cur)
sam[p].fa = 1;
else
{
int q = sam[cur].ch[x];
if(sam[cur].len + 1 == sam[q].len)
sam[p].fa = q;
else
{
nxt = ++tot;
sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
sam[cur].ch[x] = nxt;
}
}
}
int c[N + 5],a[(N << 1) + 5];
inline void init()
{
for(register int i = 1;i <= tot;++i)
++c[sam[i].len];
for(register int i = 1;i <= N;++i)
c[i] += c[i - 1];
for(register int i = tot;i > 1;--i)
a[c[sam[i].len]--] = i;
for(register int i = tot;i > 1;--i)
sz[sam[a[i]].fa] += sz[a[i]];
}
}
int q[N + 5],head,tail;
int main()
{
scanf("%d%d",&n,&k);
char ch;
int fa;
for(register int i = 1;i <= n;++i)
scanf(" %c%d",&ch,&fa),tr[++fa].ch[ch - 'A'] = i + 1;
q[tail = 1] = 1,tr[1].ed = 1;
for(register int p;head < tail;)
{
p = q[++head];
for(register int i = 0;i < 26;++i)
if(tr[p].ch[i])
SAM::las = tr[p].ed,SAM::insert(i),tr[tr[p].ch[i]].ed = SAM::las,q[++tail] = tr[p].ch[i];
}
SAM::init();
for(;k;--k)
{
scanf("%s",s + 1),m = strlen(s + 1);
int p = 1,flag = 0;
for(register int i = m;i;--i)
{
if(!SAM::sam[p].ch[s[i] - 'A'])
{
puts("0"),flag = 1;
break;
}
p = SAM::sam[p].ch[s[i] - 'A'];
}
if(!flag)
printf("%d\n",SAM::sz[p]);
}
}