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: Wrong Answer

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 = data[N]
it = iter(data[N+1:])
query = zip(it,it)

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)

compare_data = []
prefix_cnt = []
for word in S:
    data,pref = solve(word)
    compare_data.append(data)
    prefix_cnt.append(pref)

Submission status: Wrong Answer

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

"""
・trie木
・各ノードから、アルファベットごとの子ノードの番号
・親ノードの番号
・各単語に対応する、ノード番号
"""

N = int(readline())
data = tuple(read().split())
S = data[:N]
Q = data[N]
it = iter(data[N+1:])
query = zip(it,it)

S

U = 4*10**5 + 100
child = [0]*(26*U)
parent = [0] * U
word_node = [0] * U

root = 26
next_idx = 52

for x in S:
    v = root
    for y in x:
        y -= 97
        w = child[v+y]
        if w:
            v=w
            continue
        child[y] = next_idx; v = next_idx; next_idx += 26

Submission status: Wrong Answer

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

"""
・trie木
・各ノードから、アルファベットごとの子ノードの番号
・親ノードの番号
・各単語に対応する、ノード番号
"""

N = int(readline())
data = tuple(read().split())
S = data[:N]
Q = data[N]
it = iter(data[N+1:])
query = zip(it,it)

S

U = 4*10**5 + 100
child = [[0]*26 for _ in range(U)]
parent = [0] * U
word_node = [0] * U

root = 1
next_idx = 2

for x in S:
    v = root
    for y in x:
        y -= 97
        w = child[v][y]
        if w:
            v=w
            continue
        child[v][y] = next_idx; v = next_idx; next_idx += 1

Submission status: Wrong Answer

Solution code:
print "HEeLO"

Submission status: Wrong Answer

Solution code:
def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def prefix(s1, s2):
    ml = min(len(s1), len(s2))
    i = 0
    while i < ml and s1[i] == s2[i]:
        i += 1
    return -1 if i==ml else i

def main():
    n = read()
    s = [input() for _ in range(n)]
    
    t = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            t[i].append(prefix(s[i], s[j]))
    print(t)
    q = read()
    for _ in range(q):
        k, p = input().split()
        pt = {}
        for c in range(26):
            pt[p[c]] = c
        k = int(k) - 1
        lk = len(s[k])
        res = 0
        for i in range(n):
            if i == k:
                continue
            index = t[k][i]
            if index == -1:
                if len(s[i]) < lk:
                    res += 1
            else:
                if pt[s[i][index]] < pt[s[k][index]]:
                    res += 1
        print(res + 1)

main()

Submission status: Wrong Answer

Solution code:
def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def prefix(s1, s2):
    ml = min(len(s1), len(s2))
    i = 0
    while i < ml and s1[i] == s2[i]:
        i += 1
    return -1 if i==ml else i

def main():
    n = read()
    s = [input() for _ in range(n)]
    
    t = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            t[i].append(prefix(s[i], s[j]))
    print(t)
    q = read()
    for _ in range(q):
        k, p = input().split()
        k = int(k) - 1
        lk = len(s[k])
        res = 0
        for i in range(n):
            if i == k:
                continue
            index = t[k][i]
            if index == -1:
                if len(s[i]) < lk:
                    res += 1
            else:
                if p.index(s[i][index]) < p.index(s[k][index]):
                    res += 1
        print(res + 1)

main()

Submission status: Wrong Answer

Solution code:
N = int(input())
S = []
for i in range(N):
	S.append(input())
Q = int(input())
kp = []
orderd = 'abcdefghijklmnopqrstuvwxyz'
for i in range(Q):
	l = input()
	kp.append([int(l.split()[0]),l.split()[1]])
SS=sorted(S)
for i, s in enumerate(kp):
	if s[1] == orderd :
		print(SS.index(S[s[0]-1])+1)
	else :
		print(i+1)

Submission status: Wrong Answer

Solution code:
import math

def conv26to10(S,k):
    num10 = 0
    j = 0
    
    for i in reversed(range(len(S))):
        #print(i)
        key = k.find(S[i])
        num10 = key * math.pow(26,j) + num10
        #print(num10)
        j = j + 1
        
    return num10

if __name__ == '__main__':
    
    N = int(input())
    S = [str(input()) for i in range(N)] 
    Q = int(input())
    K = [[str(i) for i in input().split()] for i in range(Q)] 

    numlist = [0] * N

    for query in range(Q):
        for i in range(N):
            numlist[i] = conv26to10(S[i],K[query][1])
        target = sorted(numlist)[int(K[query][0])-1]
        print(numlist.index(target)+1)

Submission status: Wrong Answer

Solution code:
N = int(raw_input())
# N = 1
G = dict()

G[''] = {'edge':dict(), 'total' : 0}

def add_node(stri):
    if G.has_key(stri):
        G[stri]['total'] += 1
    else:
        G[stri] = {'edge':dict(), 'total' : 1}


def add_edge(stri1, stri2):
    G[stri1]['edge'][stri2] = stri1 + stri2

S_list = list()
#S_list=['abcd']
for n in range(N):
    S_list.append(raw_input())

for n in range(N):
    s = S_list[n]
    # print s
    s_ = ''
    for i in range(len(s)):
        add_node(s_+s[i])
        add_edge(s_, s[i])
        s_ += s[i]

Q = int(raw_input())
for q in range(Q):
    k_s, alphabed = raw_input().split()
    s = S_list[int(k_s) - 1]
    res = 0
    s_ = ''
    for i in range(len(s)):
        for al in alphabed:
            if al == s[i]:
                break
            elif G[s_]['edge'].has_key(al):
                res += G[s_+al]['total']
        s_ += s[i]
    print res + 1

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [input() for _ in range(N)]
Q = int(input())
S.sort()
k, p = zip(*map(lambda x: (int(x[0]), x[1]), [input().split() for _ in range(Q)]))
for q in range(Q):
    print(q)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [input() for _ in range(N)]
Q = int(input())
k, p = zip(*map(lambda x: (int(x[0]), x[1]), [input().split() for _ in range(Q)]))
for q in range(Q):
    print(q)

Submission status: Wrong Answer

Solution code:
q = None

def cmps(a,b):
    global q
    s = q[1]
    s1 = a[1]
    s2 = b[1]
    l = min(len(s1), len(s2))
    for i in xrange(l):
        p1 = s.index(s1[i])
        p2 = s.index(s2[i])
        if p1 < p2:
            return -1
        elif p1 > p2:
            return 1
    if len(s1) < len(s2):
        return -1
    elif len(s1) > len(s2):
        return 1
    return 0  

n = int(raw_input())
s = []
for i in xrange(n):
    s.append((i+1, raw_input()))

m = int(raw_input())
for i in xrange(m):
    x, y = raw_input().split()
    q = (int(x), y)
    s.sort(cmp=cmps)
    print s[q[0]-1][0]

Submission status: Wrong Answer

Solution code:
import math
import copy
N = int(raw_input().strip())
S = []
for n in xrange(0,N):
  Si = list(raw_input().strip())
  S.append("0" + "0".join(Si))
Q = int(raw_input().strip())
k = []
p = []
for q in xrange(0, Q):
  ki, pi = raw_input().strip().split()
  k.append(int(ki)-1)
  pi = (list(pi))
  p.append({ i: pii for i, pii in enumerate(pi)})

basep = "abcdefghijklmnopqrstuvwxyz"
basep = { i: pii for i, pii in enumerate(basep)}

def sort_with(pi, queryidx):
  newS = copy.deepcopy(S)
  for i in xrange(len(basep)):
    for j,Si in enumerate(newS):
      newS[j] = Si.replace("0"+pi[i], basep[i])
  print newS
  queryword = newS[queryidx]
  newS.sort()
  print newS.index(queryword)+1

for i in xrange(Q):
  sort_with(p[i], k[i])

Submission status: Time Limit Exceeded

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 < 200000:

    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: Time Limit Exceeded

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 < 100000:

    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: Time Limit Exceeded

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 = []
Slen = 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]:
            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())

if Q < 90000:

    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: Time Limit Exceeded

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 = []
bunki = 0


for loop in range(N):

    S = input()
    S += " "
    Slis.append(S)

    nind = 0

    for i in S:

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

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


if bunki > 50000:

    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)

Q = int(input())
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: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/code-festival-2016-qualb/tasks/codefestival_2016_qualB_e

普通にトライ木を構成するだけではだめだったな
各文字列1回しかたどらなければおk

テーブルを作るんだったか
答えに数字がたされるのは、ある文字(S中)がある文字より辞書順で大きいことが原因
すなわち、各文字列に対してテーブルを作っておけばいい

構築 O(Σ|S| * 26)
クエリ O(26^2 * Q) 

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


N = int(input())

c = [{}]
num = [N]

Slis = []

for loop in range(N):

    S = input()
    S += " "
    Slis.append(S)

    nind = 0

    for i in S:

        if i not in c[nind]:
            c[nind][i] = len(c)
            c.append({})
            num.append(0)

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

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)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())

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

Slis = []

for loop in range(N):

    S = input()
    S += " "
    Slis.append(S)

    nind = 0

    for i in S:

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

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

#print (c)
#print (num)

Q = int(input())
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: Time Limit Exceeded

Solution code:

N = int(input())

c = [{}]
num = [N]

Slis = []

for loop in range(N):

    S = input()
    S += " "
    Slis.append(S)

    nind = 0

    for i in S:

        if i not in c[nind]:
            c[nind][i] = len(c)
            c.append({})
            num.append(0)

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

#print (c)
#print (num)

Q = int(input())

for loop in range(Q):

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

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

    for i in Slis[k-1]:

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

        nind = c[nind][i]

    print (ans+1)

Submission status: Time Limit Exceeded

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 i in range(N):
    if not Query[i]:
        continue
    L, P = map(list, zip(*Query[i]))
    M = len(P)
    vn = T.root
    ans = [0]*M
    for si in Di[i]:        
        for idx in range(M):
            pinv = P[idx]
            for al in range(26):
                if vn[al] and pinv[al] < pinv[si]:
                    ans[idx] += vn[al].count
        vn = vn[si]
        if vn.end:
            ans = [1+a for a in ans]
    for j in range(M):
        Ans[L[j]] = ans[j]
print('\n'.join(map(str, Ans)))

Submission status: Time Limit Exceeded

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 i in range(N):
    if not Query[i]:
        continue
    L = []
    P = []
    for qu, p in Query[i]:
        L.append(qu)
        P.append(p)
    M = len(P)
    vn = T.root
    ans = [0]*M
    for si in Di[i]:        
        for al in range(26):
            for idx in range(M):
                pinv = P[idx]
                if pinv[al] < pinv[si]:
                    if vn[al] is not None:
                        ans[idx] += vn[al].count
        vn = vn[si]
        if vn.end:
            ans = [1+a for a in ans]
    for j in range(M):
        Ans[L[j]] = ans[j]
print('\n'.join(map(str, Ans)))

Submission status: Time Limit Exceeded

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 i in range(N):
    L = []
    P = []
    for qu, p in Query[i]:
        L.append(qu)
        P.append(p)
    M = len(P)
    vn = T.root
    ans = [0]*M
    for si in Di[i]:        
        for al in range(26):
            for idx in range(M):
                pinv = P[idx]
                if pinv[al] < pinv[si]:
                    if vn[al] is not None:
                        ans[idx] += vn[al].count
        vn = vn[si]
        if vn.end:
            ans = [1+a for a in ans]
    for i in range(M):
        Ans[L[i]] = ans[i]
print('\n'.join(map(str, Ans)))

Submission status: Time Limit Exceeded

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
for qu in range(Q):
    k, p = readline().strip().split()
    k = int(k)-1
    p = list(map(lambda x:ord(x)-97, p))
    vn = T.root
    res = 0
    for si in Di[k]:        
        for al in p:
            if al == si:
                break
            if vn[al] is not None:
                res += vn[al].count
        vn = vn[si]
        if vn.end:
            res += 1
    Ans[qu] = res
print('\n'.join(map(str, Ans)))