Indie Album (Codeforces 1207G)
Tags: Others, string suffix structures

Mishka's favourite experimental indie band has recently dropped a new album! Songs of that album share one gimmick. Each name $$$s_i$$$ is one of the following types:  $$$1~c$$$ — a single lowercase Latin letter;  $$$2~j~c$$$ — name $$$s_j$$$ ($$$1 \le j < i$$$) with a single lowercase Latin letter appended to its end. Songs are numbered from $$$1$$$ to $$$n$$$. It's guaranteed that the first song is always of type $$$1$$$.Vova is rather interested in the new album but he really doesn't have the time to listen to it entirely. Thus he asks Mishka some questions about it to determine if some song is worth listening to. Questions have the following format:  $$$i~t$$$ — count the number of occurrences of string $$$t$$$ in $$$s_i$$$ (the name of the $$$i$$$-th song of the album) as a continuous substring, $$$t$$$ consists only of lowercase Latin letters. Mishka doesn't question the purpose of that information, yet he struggles to provide it. Can you please help Mishka answer all Vova's questions?

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — the number of songs in the album.Each of the next $$$n$$$ lines contains the desciption of the $$$i$$$-th song of the album in the following format:  $$$1~c$$$ — $$$s_i$$$ is a single lowercase Latin letter;  $$$2~j~c$$$ — $$$s_i$$$ is the name $$$s_j$$$ ($$$1 \le j < i$$$) with a single lowercase Latin letter appended to its end. The next line contains a single integer $$$m$$$ ($$$1 \le m \le 4 \cdot 10^5$$$) — the number of Vova's questions.Each of the next $$$m$$$ lines contains the desciption of the $$$j$$$-th Vova's question in the following format:  $$$i~t$$$ ($$$1 \le i \le n$$$, $$$1 \le |t| \le 4 \cdot 10^5$$$) — count the number of occurrences of string $$$t$$$ in $$$s_i$$$ (the name of the $$$i$$$-th song of the album) as a continuous substring, $$$t$$$ consists only of lowercase Latin letters. It's guaranteed that the total length of question strings $$$t$$$ doesn't exceed $$$4 \cdot 10^5$$$.

Output: For each question print a single integer — the number of occurrences of the question string $$$t$$$ in the name of the $$$i$$$-th song of the album as a continuous substring.

Note: Song names of the first example:  d  da  dad  dada  dadad  dadada  dadadad  dadadada  d  do  dok  doki  dokid  dokido  dokidok  dokidoki  do  dok  doki  dokidoki Thus the occurrences for each question string are:  string "da" starts in positions $$$[1, 3, 5, 7]$$$ in the name "dadadada";  string "dada" starts in positions $$$[1, 3, 5]$$$ in the name "dadadada";  string "ada" starts in positions $$$[2, 4, 6]$$$ in the name "dadadada";  string "dada" starts in positions $$$[1, 3]$$$ in the name "dadada";  no occurrences of string "dada" in the name "dad";  string "doki" starts in position $$$[1]$$$ in the name "doki";  string "ok" starts in position $$$[2]$$$ in the name "doki";  string "doki" starts in positions $$$[1, 5]$$$ in the name "dokidoki";  string "doki" starts in position $$$[1]$$$ in the name "dokidok";  string "d" starts in position $$$[1]$$$ in the name "d";  no occurrences of string "a" in the name "d";  string "doki" starts in positions $$$[1, 5]$$$ in the name "dokidoki". 

Sample Inputs:
20
1 d
2 1 a
2 2 d
2 3 a
2 4 d
2 5 a
2 6 d
2 7 a
1 d
2 9 o
2 10 k
2 11 i
2 12 d
2 13 o
2 14 k
2 15 i
2 1 o
2 17 k
2 18 i
2 15 i
12
8 da
8 dada
8 ada
6 dada
3 dada
19 doki
19 ok
16 doki
15 doki
9 d
1 a
20 doki

Sample Outputs:
4
3
3
2
0
1
1
2
1
1
0
2

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph(n, m):
    s = [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        s[x[i] + 2] += 1
    for i in range(2, n + 3):
        s[i] += s[i - 1]
    (G, W) = ([0] * m, [0] * m)
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        W[s[j]] = y[i ^ 1]
        s[j] += 1
    return (G, W, s)

def insert(s, G, w):
    j = 0
    for i in s:
        Gj = G[j]
        if len(Gj) <= i or not Gj[i] ^ -1:
            Gj[i] = len(G)
            G.append([-1] * w)
            j = len(G) - 1
        else:
            j = Gj[i]
    return j

def aho_corasick(s, w):
    G = [[-1] * w]
    v = []
    for s0 in s:
        x = insert(s0, G, w)
        v.append(x)
    G0 = G[0]
    for i in range(w):
        G0[i] = max(G0[i], 0)
    l = len(G)
    f = [0] * l
    (q, z) = ([0], 0)
    dist = [-1] * l
    dist[0] = 0
    while len(q) ^ z:
        i = q[z]
        di = dist[i]
        Gi = G[i]
        for j in range(len(Gi)):
            k = Gi[j]
            if k <= 0:
                continue
            q.append(k)
            dist[k] = di + 1
            if not di:
                continue
            u = i
            while True:
                u = f[u]
                if len(G[u]) > j and G[u][j] ^ -1:
                    f[k] = G[u][j]
                    break
        z += 1
    return (G, f, v, q)

def fenwick_tree(n):
    tree = [0] * (n + 1)
    return tree

def get_sum0(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum(s, t):
    ans = 0 if s > t else get_sum0(t) - get_sum0(s - 1)
    return ans

def add(i, x):
    while i < len(tree):
        tree[i] += x
        i += i & -i

def g(u, v):
    return u * l + v
n = int(input())
x = [0] * (2 * n)
y = [0] * (2 * n)
for i in range(n):
    z = list(input().rstrip().decode().split())
    if z[0] == '1':
        (j, c) = (0, ord(z[1]) - 97)
    else:
        (j, c) = (int(z[1]), ord(z[2]) - 97)
    (x[2 * i], x[2 * i + 1]) = (j, i + 1)
    (y[2 * i], y[2 * i + 1]) = (c, c)
(G1, W1, s1) = make_graph(n + 1, n)
m = int(input())
s = []
(x, y) = ([0] * (2 * m), [0] * (2 * m))
for j in range(m):
    (i, t) = input().rstrip().decode().split()
    s.append([ord(k) - 97 for k in t])
    (x[2 * j], x[2 * j + 1]) = (int(i), j)
(G2, _, s2) = make_graph(n + 1, m)
(G, f, v, q) = aho_corasick(s, 26)
l = len(f)
x = [0] * (2 * (l - 1))
y = [0] * (2 * (l - 1))
for i in range(l - 1):
    (x[2 * i], x[2 * i + 1]) = (f[i + 1], i + 1)
(G3, _, s3) = make_graph(l, l - 1)
st = [0]
(ll, rr, t) = ([1] * l, [1] * l, 1)
now = list(s3)
while st:
    i = st[-1]
    t += 1
    if now[i] ^ s3[i + 1]:
        j = G3[now[i]]
        now[i] += 1
        ll[j] = t
        st.append(j)
    else:
        rr[i] = t
        st.pop()
dp = [0] * (26 * l)
for i in range(26):
    for j in q[1:]:
        dp[g(i, j)] = dp[g(i, f[j])] if G[j][i] == -1 else j
tree = fenwick_tree(2 * l + 5)
st = [0]
e = [0]
now = list(s1)
ans = [0] * m
while st:
    i = st[-1]
    if now[i] ^ s1[i + 1]:
        (j, c, k) = (G1[now[i]], W1[now[i]], e[-1])
        now[i] += 1
        st.append(j)
        k = G[dp[g(c, k)]][c]
        e.append(k)
        add(ll[k], 1)
        for z in range(s2[j], s2[j + 1]):
            i = G2[z]
            ans[i] = get_sum(ll[v[i]], rr[v[i]])
    else:
        j = st.pop()
        k = e.pop()
        add(ll[k], -1)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph(n, m):
    s = [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        s[x[i] + 2] += 1
    for i in range(2, n + 3):
        s[i] += s[i - 1]
    (G, W) = ([0] * m, [0] * m)
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        W[s[j]] = y[i ^ 1]
        s[j] += 1
    return (G, W, s)

def g(u, v):
    return 26 * u + v

def insert(s, G, la):
    i = 0
    for j in s:
        if G[g(i, j)] == -1:
            la += 1
            G[g(i, j)] = la
        i = G[g(i, j)]
    return (i, la)

def aho_corasick(s, w):
    l = 1
    for s0 in s:
        l += len(s0)
    G = [-1] * (l * w)
    (v, la) = ([], 0)
    for s0 in s:
        (x, la) = insert(s0, G, la)
        v.append(x)
    for i in range(w):
        G[i] = max(G[i], 0)
    l = la + 1
    f = [0] * l
    (q, z) = ([0], 0)
    dist = [-1] * l
    dist[0] = 0
    while len(q) ^ z:
        i = q[z]
        di = dist[i]
        for j in range(w):
            k = G[g(i, j)]
            if k <= 0:
                continue
            q.append(k)
            dist[k] = di + 1
            if not di:
                continue
            u = i
            while True:
                u = f[u]
                if G[g(u, j)] ^ -1:
                    f[k] = G[g(u, j)]
                    break
        z += 1
    return (G, f, v, q)

def fenwick_tree(n):
    tree = [0] * (n + 1)
    return tree

def get_sum0(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum(s, t):
    ans = 0 if s > t else get_sum0(t) - get_sum0(s - 1)
    return ans

def add(i, x):
    while i < len(tree):
        tree[i] += x
        i += i & -i
n = int(input())
x = [0] * (2 * n)
y = [0] * (2 * n)
for i in range(n):
    z = list(input().rstrip().decode().split())
    if z[0] == '1':
        (j, c) = (0, ord(z[1]) - 97)
    else:
        (j, c) = (int(z[1]), ord(z[2]) - 97)
    (x[2 * i], x[2 * i + 1]) = (j, i + 1)
    (y[2 * i], y[2 * i + 1]) = (c, c)
(G1, W1, s1) = make_graph(n + 1, n)
m = int(input())
s = []
(x, y) = ([0] * (2 * m), [0] * (2 * m))
for j in range(m):
    (i, t) = input().rstrip().decode().split()
    s.append([ord(k) - 97 for k in t])
    (x[2 * j], x[2 * j + 1]) = (int(i), j)
(G2, _, s2) = make_graph(n + 1, m)
(G, f, v, q) = aho_corasick(s, 26)
l = len(f)
x = [0] * (2 * (l - 1))
y = [0] * (2 * (l - 1))
for i in range(l - 1):
    (x[2 * i], x[2 * i + 1]) = (f[i + 1], i + 1)
(G3, _, s3) = make_graph(l, l - 1)
st = [0]
(ll, rr, t) = ([1] * l, [1] * l, 1)
now = list(s3)
while st:
    i = st[-1]
    t += 1
    if now[i] ^ s3[i + 1]:
        j = G3[now[i]]
        now[i] += 1
        ll[j] = t
        st.append(j)
    else:
        rr[i] = t
        st.pop()
dp = [0] * (26 * l)
for j in range(26):
    for i in q[1:]:
        dp[g(i, j)] = dp[g(f[i], j)] if G[g(i, j)] == -1 else i
tree = fenwick_tree(2 * l + 5)
st = [0]
e = [0]
now = list(s1)
ans = [0] * m
while st:
    i = st[-1]
    if now[i] ^ s1[i + 1]:
        (j, c, k) = (G1[now[i]], W1[now[i]], e[-1])
        now[i] += 1
        st.append(j)
        k = G[g(dp[g(k, c)], c)]
        e.append(k)
        add(ll[k], 1)
        for z in range(s2[j], s2[j + 1]):
            i = G2[z]
            ans[i] = get_sum(ll[v[i]], rr[v[i]])
    else:
        j = st.pop()
        k = e.pop()
        add(ll[k], -1)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph(n, m):
    s = [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        s[x[i] + 2] += 1
    for i in range(2, n + 3):
        s[i] += s[i - 1]
    (G, W) = ([0] * m, [0] * m)
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        W[s[j]] = y[i ^ 1]
        s[j] += 1
    return (G, W, s)

def g(u, v):
    return 26 * u + v

def insert(s, G, la):
    i = 0
    for j in s:
        if G[g(i, j)] == -1:
            la += 1
            G[g(i, j)] = la
        i = G[g(i, j)]
    return (i, la)

def aho_corasick(s, w):
    l = 1
    for s0 in s:
        l += len(s0)
    G = [-1] * (l * w)
    (v, la) = ([], 0)
    for s0 in s:
        (x, la) = insert(s0, G, la)
        v.append(x)
    for i in range(w):
        G[i] = max(G[i], 0)
    l = la + 1
    f = [0] * l
    (q, z) = ([0], 0)
    dist = [-1] * l
    dist[0] = 0
    while len(q) ^ z:
        i = q[z]
        di = dist[i]
        for j in range(w):
            k = G[g(i, j)]
            if k <= 0:
                continue
            q.append(k)
            dist[k] = di + 1
            if not di:
                continue
            u = i
            while True:
                u = f[u]
                if G[g(u, j)] ^ -1:
                    f[k] = G[g(u, j)]
                    break
        z += 1
    return (G, f, v, q)

def fenwick_tree(n):
    tree = [0] * (n + 1)
    return tree

def get_sum0(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum(s, t):
    ans = 0 if s > t else get_sum0(t) - get_sum0(s - 1)
    return ans

def add(i, x):
    while i < len(tree):
        tree[i] += x
        i += i & -i
n = int(input())
x = [0] * (2 * n)
y = [0] * (2 * n)
for i in range(n):
    z = list(input().rstrip().decode().split())
    if z[0] == '1':
        (j, c) = (0, ord(z[1]) - 97)
    else:
        (j, c) = (int(z[1]), ord(z[2]) - 97)
    (x[2 * i], x[2 * i + 1]) = (j, i + 1)
    (y[2 * i], y[2 * i + 1]) = (c, c)
(G1, W1, s1) = make_graph(n + 1, n)
m = int(input())
s = []
(x, y) = ([0] * (2 * m), [0] * (2 * m))
for j in range(m):
    (i, t) = input().rstrip().decode().split()
    s.append([ord(k) - 97 for k in t])
    (x[2 * j], x[2 * j + 1]) = (int(i), j)
(G2, _, s2) = make_graph(n + 1, m)
(G, f, v, q) = aho_corasick(s, 26)
l = len(f)
x = [0] * (2 * (l - 1))
y = [0] * (2 * (l - 1))
for i in range(l - 1):
    (x[2 * i], x[2 * i + 1]) = (f[i + 1], i + 1)
(G3, _, s3) = make_graph(l, l - 1)
st = [0]
(ll, rr, t) = ([1] * l, [1] * l, 1)
now = list(s3)
while st:
    i = st[-1]
    t += 1
    if now[i] ^ s3[i + 1]:
        j = G3[now[i]]
        now[i] += 1
        ll[j] = t
        st.append(j)
    else:
        rr[i] = t
        st.pop()
dp = [0] * (26 * l)
for j in range(26):
    for i in q[1:]:
        dp[g(i, j)] = dp[g(f[i], j)] if G[g(i, j)] == -1 else i
tree = fenwick_tree(2 * l + 5)
st = [0]
e = [0]
now = list(s1)
ans = [0] * m
while st:
    i = st[-1]
    if now[i] ^ s1[i + 1]:
        (j, c, k) = (G1[now[i]], W1[now[i]], e[-1])
        now[i] += 1
        st.append(j)
        k = G[g(dp[g(k, c)], c)]
        e.append(k)
        add(ll[k], 1)
        for z in range(s2[j], s2[j + 1]):
            i = G2[z]
            ans[i] = get_sum(ll[v[i]], rr[v[i]])
    else:
        j = st.pop()
        k = e.pop()
        add(ll[k], -1)
sys.stdout.write('\n'.join(map(str, ans)))