Problem:


Score : 1100 points

Problem Statement

There are N strings of lowercase alphabet only. The i-th string is S_i. Every string is unique.

Provide answers for the Q queries below. The i-th query has the following format:

Query: An integer k_i and a string p_{i,1}p_{i,2}...p_{i,26} that results from permuting {a,b,...,z} are given. Output the sequence of the string S_{k_i} among the N strings in lexicographical order when the literal sequence is p_{i,1}<p_{i,2}<...<p_{i,26}.

Constraints

1 ≦ N,Q ≦ 100000

1 ≦ |S_i| (1 ≦ i ≦ N)

S_i (1 ≦ i ≦ N) is a string of lowercase alphabet.

The sum of |S_i| is no more than 400000.

Every S_i is unique.

1 ≦ k_i ≦ N (1 ≦ i ≦ Q)

For all 1 ≦ i ≦ Q, p_{i,1}p_{i,2}...p_{i,26} is a permutation of abcd...z.

Input

Inputs are provided from standard inputs in the following form.

N
S_1
:
S_N
Q
k_1 p_{1,1}p_{1,2}...p_{1,26}
:
k_Q p_{Q,1}p_{Q,2}...p_{Q,26}

Output

Output Q lines.

On line i, for the i-th query, output an integer indicating the sequence of the string S_{k_i} among the N strings in lexicographical order.

Sample Input 1

5
aa
abbaa
abbba
aaab
aaaaaba
5
1 abcdefghijklmnopqrstuvwxyz
2 bacdefghijklmnopqrstuvwxyz
3 abcdefghijklmnopqrstuvwxyz
4 bacdefghijklmnopqrstuvwxyz
5 abcdefghijklmnopqrstuvwxyz

Sample Output 1

1
2
5
4
2

When the literal sequence is a < b, sorting the input strings in lexicographical order yields aa, aaaaaba, aaab, abbaa, abbba. The answers to queries 1, 3, and 5 are thus 1, 5, and 2, respectively.

When the literal sequence is b < a, sorting the input strings in lexicographical order yields abbba, abbaa, aa, aaab, aaaaaba. The answers to queries 2 and 4 are thus 2 and 4, respectively.

Sample Input 2

8
abrakatabra
abadaba
abracadabra
atcoder
grand
contest
ababa
a
6
3 abcdefghijklmnopqrstuvwxyz
6 qwertyuiopasdfghjklzxcvbnm
8 poiuytrewqlkjhgfdsamnbvcxz
2 qazwsxedcrfvtgbyhnujmikolp
1 plokmijnuhbygvtfcrdxeszwaq
4 mnbvcxzasdfghjklpoiuytrewq

Sample Output 2

4
8
2
3
4
7



Sample input:
5
aa
abbaa
abbba
aaab
aaaaaba
5
1 abcdefghijklmnopqrstuvwxyz
2 bacdefghijklmnopqrstuvwxyz
3 abcdefghijklmnopqrstuvwxyz
4 bacdefghijklmnopqrstuvwxyz
5 abcdefghijklmnopqrstuvwxyz


Sample output:
1
2
5
4
2

Submission status: Accepted

Solution code:

import sys

alp = "abcdefghijklmnopqrstuvwxyz"
D = {}
for i in range(26):
    D[alp[i]] = i 


N = int(input())

c = [{}]
num = [N]
dep = [0]

Slis = []
lon = 0


for loop in range(N):

    S = input()
    S += " "
    Slis.append(S)
    #Slen += len(S)

    nind = 0

    for i in S:

        if i not in c[nind]:
            lon += 1
            if len(c[nind]) == 1:
                lon -= 1
            c[nind][i] = len(c)
            c.append({})
            num.append(0)
            dep.append(dep[nind]+1)


        nind = c[nind][i]
        num[nind] += 1

Q = int(input())
#print (lon)

if lon < 70000:

    always = [0] * N
    table = []

    #print (c)
    #print (num)

    #table構築
    for loop in range(N):

        nt = [[0] * 26 for i in range(26)]
        nind = 0

        for i in Slis[loop]:

            if i == " ":
                continue

            #print ("now char",i)

            for j in c[nind]:
                #print ("nowj",j)
                if j == " ":
                    always[loop] += 1
                    #print ("always pl+1")
                elif j != i:
                    #print ("if",i,">",j,"plus:",num[c[nind][j]])
                    nt[D[i]][D[j]] += num[c[nind][j]]

            nind = c[nind][i]

        table.append(nt)

    #print (always)
    #print (table[0])

    #Q = int(input())

    for loop in range(Q):

        k,p = input().split()
        k = int(k)
        k-=1
    
        ans = always[k] + 1

        for i in range(26):
            for j in range(i):

                ind1 = D[p[i]]
                ind2 = D[p[j]]

                ans += table[k][ind1][ind2]

        print (ans)

    sys.exit()




#print (c)
#print (num)


lpc = 0

for loop in range(Q):

    k,p = input().split()
    k = int(k)

    p = " " + p
    nind = 0
    ans = 0

    ncr = 0

    while ncr < len(Slis[k-1]):

        i = Slis[k-1][ncr]

        for j in p:
            if j == i:
                break
            
            elif j in c[nind]:
                ans += num[c[nind][j]]

        while len( c[c[nind][i]] ) == 1:
            for x in c[c[nind][i]]:
                c[nind][i] = c[c[nind][i]][x]
            
        nind = c[nind][i]
        ncr = dep[nind]

    print (ans+1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
class Node:
    def __init__(self, sigma, depth):
        self.end = False
        self.child = [None] * sigma
        self.depth = depth
        self.count = 0
    def __setitem__(self, i, x):
        self.child[i] = x
    def __getitem__(self, i):
        return self.child[i]

class Trie():
    def __init__(self, sigma):
        self.sigma = sigma
        self.root = Node(sigma, 0)
    
    def add(self, S):
        vn = self.root
        vn.count += 1
        for cs in S:
            if vn[cs] is None:
                vn[cs] = Node(self.sigma, vn.depth + 1)
            vn = vn[cs]
            vn.count += 1
        vn.end = True

T = Trie(26)
N = int(readline())
Di = [None]*N

for i in range(N):
    S = list(map(lambda x: ord(x)-97, readline().strip()))
    Di[i] = S
    T.add(S)

Q = int(readline())
Ans = [None]*Q
Query = [[] for _ in range(N)]
for qu in range(Q):
    k, p = readline().strip().split()
    k = int(k)-1
    p = list(map(lambda x:ord(x)-97, p))
    pinv = [None]*26
    for i in range(26):
        pinv[p[i]] = i
    Query[k].append((qu, pinv))

for k in range(N):
    if not Query[k]:
        continue
    cost = [[0]*26 for _ in range(26)]
    geta = 0
    vn = T.root
    for si in Di[k]:        
        for ti in range(26):
            if si != ti and vn[ti] is not None:
                cost[si][ti] += vn[ti].count
        vn = vn[si]
        if vn.end:
            geta += 1
    L, P = map(list, zip(*Query[k]))
    M = len(P)
    for idx in range(M):
        res = 0
        invp = P[idx]
        for i in range(26):
            for j in range(26):
                if invp[i] > invp[j]:
                    res += cost[i][j]
        Ans[L[idx]] = res+geta
        
print('\n'.join(map(str, Ans)))

Submission status: Accepted

Solution code:
# 文字列の問題で、同じような文字列をまとめたいので、
# どう考えても Trie を使いたい気持ちになる

# あとは適当にやったらなんとかなった
# 1100 点の割には簡単っぽい

class TrieNode:
    def __init__(self):
        self.child = {}
        self.count = 0  # 自身を含めた部分木の大きさ

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def add(self, s):
        node = self.root
        node.count += 1
        for c in s:
            c = ord(c) - 97
            if c not in node.child:
                node.child[c] = TrieNode()
            node = node.child[c]
            node.count += 1
        node.child[26] = TrieNode()
        node.child[26].count += 1

    def query(self, s):
        res = [[0]*27 for _ in range(26)]
        node = self.root
        for c in s:
            c = ord(c) - 97
            res_c = res[c]
            for i, child in node.child.items():
                res_c[i] += child.count
            node = node.child[c]
        return res

from itertools import groupby
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    S = [input()[:-1] for _ in range(N)]
    trie = Trie()
    for s in S:
        trie.add(s)

    Q = int(input())
    KP = [input().split() for _ in range(Q)]
    Ans = [-1] * Q
    Idx_Q = sorted(range(Q), key=lambda x: KP[x][0])
    for v, g in groupby(Idx_Q, key=lambda x: KP[x][0]):
        K = int(v) - 1
        L_K = trie.query(S[K])
        for idx in g:
            _, P = KP[idx]
            P = [ord(c) - 97 for c in P]
            ans = 1
            for i, pi in enumerate(P):
                for pj in P[:i]:
                    ans += L_K[pi][pj]
                ans += L_K[pi][26]
            Ans[idx] = ans
    print("\n".join(map(str, Ans)))

main()

Submission status: Accepted

Solution code:
# 文字列の問題で、同じような文字列をまとめたいので、
# どう考えても Trie を使いたい気持ちになる

# あとは適当にやったらなんとかなった
# 1100 点の割には簡単っぽい

class TrieNode:
    def __init__(self):
        self.child = {}
        self.count = 0  # 自身を含めた部分木の大きさ

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def add(self, s):
        node = self.root
        node.count += 1
        for c in s:
            c = ord(c) - 97
            if c not in node.child:
                node.child[c] = TrieNode()
            node = node.child[c]
            node.count += 1
        node.child[26] = TrieNode()
        node.child[26].count += 1

    def query(self, s):
        res = [[0]*27 for _ in range(26)]
        node = self.root
        for c in s:
            c = ord(c) - 97
            res_c = res[c]
            for i, child in node.child.items():
                res_c[i] += child.count
            node = node.child[c]
        return res

from itertools import groupby
import sys
input = sys.stdin.readline
N = int(input())
S = [input()[:-1] for _ in range(N)]
trie = Trie()
for s in S:
    trie.add(s)

Q = int(input())
KP = [input().split() for _ in range(Q)]
Ans = [-1] * Q
Idx_Q = sorted(range(Q), key=lambda x: KP[x][0])
for v, g in groupby(Idx_Q, key=lambda x: KP[x][0]):
    K = int(v) - 1
    L_K = trie.query(S[K])
    for idx in g:
        _, P = KP[idx]
        P = [ord(c) - 97 for c in P]
        ans = 1
        for i, pi in enumerate(P):
            for pj in P[:i]:
                ans += L_K[pi][pj]
            ans += L_K[pi][26]
        Ans[idx] = ans
print("\n".join(map(str, Ans)))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import defaultdict

"""
・trie木
・各ノードから、アルファベットごとの子ノードの番号
・親ノードの番号
"""

N = int(readline())
data = tuple(read().split())
S = data[:N]
Q = int(data[N])
query_target = list(map(int,data[N+1::2]))
query_order = data[N+2::2]

class Node():
    def __init__(self,parent):
        self.parent=parent
        self.child = defaultdict(int)
        self.is_word_node = False
        self.Nword = 0 # 部分木にあるword_nodeの個数
        
    def __repr__(self):
        return 'parent:{}\nchild:{}\nNword:{}'.format(self.parent,self.child,self.Nword)

def add(word):
    n = 0
    next_idx = len(nodes)
    for x in word:
        nodes[n].Nword += 1
        c = nodes[n].child[x]
        if c == 0:
            c = next_idx
            nodes[n].child[x] = c
            nodes.append(Node(n))
            next_idx += 1
        n = c
    nodes[n].is_word_node = True
    nodes[n].Nword += 1

def solve(word):
    """
    ・wordに沿って進む。
    ・「char1<char2ならば自身より弱い文字列1個」という情報を調べる・
    ・自身のprefixの個数も調べる
    """
    data = defaultdict(int)
    prefix = 0
    n = 0
    for x in word:
        # 進む前に、他のルートの文字列数も確認する
        for k,v in nodes[n].child.items():
            if k == x:
                continue
            data[1000*k+x] += nodes[v].Nword # k<xのときの加算量
        # prefixを見つけたら加算
        if nodes[n].is_word_node:
            prefix += 1
        # 進む
        n = nodes[n].child[x]
    return data, prefix

root = Node(0)
nodes = [root]

for word in S:
    add(word)

# 同じ文字列に対するクエリを一括処理
word_to_query = [[] for _ in range(N)]
for i,x in enumerate(query_target):
    word_to_query[x-1].append(i)

answer = [0]*Q
for n,word in enumerate(S):
    if not word_to_query[n]:
        continue
    data,pref = solve(word)
    for q in word_to_query[n]:
        order = query_order[q]
        alphabet_rank = {x:i for i,x in enumerate(order)}
        rank = pref+1
        for x,v in data.items():
            a,b = divmod(x,1000)
            if alphabet_rank[a] < alphabet_rank[b]:
                rank += v
        answer[q] = rank

print('\n'.join(map(str,answer)))

Submission status: Accepted

Solution code:
import array;R=range;L=input;T=[0]*28;N=int(L());S=[[ord(C)-95 for C in L()]for _ in[0]*N];U=N*26**2*array.array('i',[0]);V=N*[0];Q=int(L())
for X in S:
	P=0
	for C in X:
		if T[P+C]==0:T[P+C]=len(T);T+=[0]*28
		T[P]+=1;P=T[P+C]
	T[P]+=1;T[P+1]=1
while N:
	N-=1;P=0
	for C in S[N]:
		for A in R(26):X=T[P+A+2];U[676*N+26*A+C-2]+=T[X]*(X and A!=C-2)
		V[N]+=T[P+1];P=T[P+C]
while Q:K,P=L().split();K=int(K)-1;P=[ord(C)-97 for C in P];X=1+V[K]+sum(U[676*K+26*P[A]+P[B]]for A in R(26)for B in R(A+1,26));print(X);Q-=1

Submission status: Accepted

Solution code:
import array;R=range;L=input;T=[0]*28;N=int(L());S=[[ord(C)-95 for C in L()]for _ in[0]*N];U=N*26**2*array.array('i',[0]);V=N*[0];Q=int(L())
for X in S:
	P=0
	for C in X:
		if T[P+C]==0:T[P+C]=len(T);T+=[0]*28
		T[P]+=1;P=T[P+C]
	T[P]+=1;T[P+1]=1
while N:
	N-=1;P=0
	for C in S[N]:
		for A in R(26):
			X=T[P+A+2]
			if(A!=C-2)*X:U[676*N+26*A+C-2]+=T[X]
		V[N]+=T[P+1]
		P=T[P+C]
while Q:
	K,P=L().split();K=int(K)-1;P=[ord(C)-97 for C in P];X=1+V[K]
	for A in R(26):
		for B in R(A+1,26):
			X+=U[676*K+26*P[A]+P[B]]
	print(X);Q-=1

Submission status: Accepted

Solution code:
from array import*;R=range;T=[0]*28;N=int(input());S=[[ord(C)-95 for C in input()]for _ in[0]*N];U=N*26**2*array('i',[0]);V=N*[0];Q=int(input())
for X in S:
	P=0
	for C in X:
		if T[P+C]==0:T[P+C]=len(T);T+=[0]*28
		T[P]+=1;P=T[P+C]
	T[P]+=1;T[P+1]=1
for I in R(N):
	P=0
	for C in S[I]:
		for A in R(26):
			X=T[P+A+2]
			if(A!=C-2)*X:U[676*I+26*A+C-2]+=T[X]
		V[I]+=T[P+1]
		P=T[P+C]
while Q:
	K,P=input().split();K=int(K)-1;P=[ord(C)-97 for C in P];X=1+V[K]
	for A in R(26):
		for B in R(A+1,26):
			X+=U[676*K+26*P[A]+P[B]]
	print(X);Q-=1

Submission status: Runtime Error

Solution code:
import array;R=range;L=input;T=[0]*28;N=int(L());S=[];U=N*26**2*array.array('i',[0]);V=N*[0];Q=int(L())
for I in R(N):
	S+=[[ord(C)-95 for C in L()]];P=0
	for C in S[I]:
		if T[P+C]==0:T[P+C]=len(T);T+=[0]*28
		T[P]+=1;P=T[P+C]
	T[P]+=1;T[P+1]=1
while N:
	N-=1;P=0
	for C in S[N]:
		for A in R(26):
			X=T[P+A+2]
			if(A!=C-2)*X:U[676*N+26*A+C-2]+=T[X]
		V[N]+=T[P+1]
		P=T[P+C]
while Q:
	K,P=L().split();K=int(K)-1;P=[ord(C)-97 for C in P];X=1+V[K]
	for A in R(26):
		for B in R(A+1,26):
			X+=U[676*K+26*P[A]+P[B]]
	print(X);Q-=1