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

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)

answer = []
for n,order in query:
    n = int(n)-1
    d = compare_data[n]
    rank=1+prefix_cnt[n]
    for j in range(1,26):
        for i in range(j):
            x = order[i]; y = order[j]
            rank += d[1000*x+y]
    answer.append(rank)

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

Submission status: Time Limit Exceeded

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

Solution code:
T=[[0,0,[-1]*26]]
N=int(input())
S=[[ord(C)-97 for C in input()]for _ in[0]*N]
for X in S:
    P=0
    for C in X:
        if T[P][2][C]<0:
            T[P][2][C]=len(T)
            T+=[[0,0,[-1]*26]]
        T[P][0]+=1
        P=T[P][2][C]
    T[P][0]+=1
    T[P][1]=1
U=N*26**2*[0]
V=N*[0]
for I in range(N):
    P=0
    for C in S[I]:
        for A in range(26):
            X=T[P][2][A]
            if X>=0 and A!=C:
                U[676*I+26*A+C]+=T[X][0]
        V[I]+=T[P][1]
        P=T[P][2][C]
Q=int(input())
for I in range(Q):
    K,P=input().split()
    K=int(K)-1
    P=[ord(C)-97 for C in P]
    X=1+V[K]
    for A in range(26):
        for B in range(A+1,26):
            X+=U[676*K+26*P[A]+P[B]]
    print(X)

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
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()

# input 
for n in range(N):
    s = raw_input()
    S_list.append(s)
    s_ = ''
    for i in range(len(s)):
        add_node(s_+s[i])
        add_edge(s_, s[i])
        s_ += s[i]
    add_node(s+'0')
    add_edge(s, '0')

# pre compute
res_dict = dict()
for n in range(N):
    s = S_list[n]
    res_dict[n] = dict()
    for l1 in '0abcdefghijklmnopqrstuvwxyz':
        res_dict[n][l1] = dict()
        for l2 in '0abcdefghijklmnopqrstuvwxyz':
            res_dict[n][l1][l2] = 0
    s_ = ''
    for i in range(len(s)):
        for l1 in G[s_]['edge'].keys():
            if l1 == s[i]:
                pass
            else:
                res_dict[n][l1][s[i]] += G[s_+l1]['total']
        s_ += s[i]
            

Q = int(raw_input())
for q in range(Q):
    k_s, alphabed = raw_input().split()
    alphabed_ = '0' + alphabed
    res = 0
    for i in range(len(alphabed_)):
        for j in range(i+1, len(alphabed_)):
            res += res_dict[int(k_s)-1][alphabed_[i]][alphabed_[j]]
    print res + 1

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
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()

# input 
for n in range(N):
    s = raw_input()
    S_list.append(s)
    s_ = ''
    for i in range(len(s)):
        add_node(s_+s[i])
        add_edge(s_, s[i])
        s_ += s[i]
    add_node(s+'0')
    add_edge(s, '0')

# pre compute
res_dict = dict()
for n in range(N):
    s = S_list[n]
    res_dict[n] = dict()
    for l1 in '0abcdefghijklmnopqrstuvwxyz':
        res_dict[n][l1] = dict()
        for l2 in '0abcdefghijklmnopqrstuvwxyz':
            res_dict[n][l1][l2] = 0
    s_ = ''
    for i in range(len(s)):
        for l1 in '0abcdefghijklmnopqrstuvwxyz':
            if l1 == s[i]:
                pass
            elif G[s_]['edge'].has_key(l1):
                res_dict[n][l1][s[i]] += G[s_+l1]['total']
        s_ += s[i]
            

Q = int(raw_input())
for q in range(Q):
    k_s, alphabed = raw_input().split()
    alphabed_ = '0' + alphabed
    res = 0
    for i in range(len(alphabed_)):
        for j in range(i+1, len(alphabed_)):
            res += res_dict[int(k_s)-1][alphabed_[i]][alphabed_[j]]
    print res + 1

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
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()

for n in range(N):
    s = raw_input()
    S_list.append(s)
    s_ = ''
    for i in range(len(s)):
        add_node(s_+s[i])
        add_edge(s_, s[i])
        s_ += s[i]
    add_node(s+'0')
    add_edge(s, '0')

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

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]
    add_node(s+'0')
    add_edge(s, '0')

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

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]))

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

Solution code:

def myQSort(strs, order, i):
	if len(strs) <= 1:
		return strs
	if len(strs[0])<=i:
		return [strs[0]]+myQSort(strs[1:],order,i)
	l = []
	g = []
	e = [strs[0]]
	p = strs[0][i]
	for s in strs[1:]:
		if len(s)<=i:
			l.append(s)
		elif p==s[i]:
			e.append(s)
		elif order.index(p)>order.index(s[i]):
			l.append(s)
		else:
			g.append(s)
	# print('s: ', strs)
	# print('l: ', l)
	# print('g: ', g)
	# print('e: ', e)
	return myQSort(l,order,i)+myQSort(e,order,i+1)+myQSort(g,order,i)

N = int(input())
S = []
for i in range(N):
	S.append(input())
Q = int(input())
kp = []
for i in range(Q):
	l = input()
	kp.append([int(l.split()[0]),l.split()[1]])
for i, s in enumerate(kp):
	SS=myQSort(S,s[1],0)
	#print(SS)
	print(SS.index(S[s[0]-1])+1)

Submission status: Time Limit Exceeded

Solution code:
def myQSort(strr, order):
	if len(strr) <= 1:
		return strr
	p = strr[0]
	#print('s: ',strr)
	#print('p: ',p)
	l = [x for x in strr[1:] if mySmaller(p,x,order) == 2]
	#print('l: ',l)
	g = [x for x in strr[1:] if mySmaller(p,x,order) == 1]
	#print('g: ',g)
	return myQSort(l,order)+[p]+myQSort(g,order)

def mySmaller(str1,str2,order):
	i=0
	if len(str1) > len(str2):
		l = len(str2)
		sub = 2
	elif len(str1) < len(str2): 
		l = len(str1)
		sub = 1
	else:
		l = len(str2)
		sub = 0
	for i in range(l):
		if order.index(str1[i])>order.index(str2[i]):
			return 2
		elif order.index(str1[i])<order.index(str2[i]):
			return 1
	return sub

N = int(input())
S = []
for i in range(N):
	S.append(input())
Q = int(input())
kp = []
for i in range(Q):
	l = input()
	kp.append([int(l.split()[0]),l.split()[1]])
for i, s in enumerate(kp):
	SS=myQSort(S,s[1])
	#print(S[s[0]-1],' among ',SS)
	print(SS.index(S[s[0]-1])+1)

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
S = []
for i in range(N):
    S.append(raw_input())

Q = int(raw_input())
for _ in range(Q):
    k, P = raw_input().split()
    k = int(k)
    ans = 0
    d_S = S
    for j, s in enumerate(S[k-1]):
        _S = d_S
        if len(d_S) == 1:
            break
        d_S = []
        i = P.index(s)
        for _s in _S:
            try:
                if _s[j] in P[:i]:
                    ans += 1
                elif _s[j] == P[i]:
                    d_S.append(_s)
            except IndexError:
                ans += 1
    print ans+1

Submission status: Time Limit Exceeded

Solution code:
S = []
for i in range(int(input())):
    S.append(input())

k = 0

cache = {}
for i in range(int(input())):
    k, pl = input().split()
    p = [i for i in pl]
    k = int(k)-1

    def comp(x, y):
        global p
        if len(x) == 1 and len(y) == 1:
            return p.index(x) - p.index(y)
        for i in range(min(len(x),len(y))):
            if x[i] == y[i]:
                continue
            return p.index(x[i]) - p.index(y[i])
        return min(len(x),len(y)) - len(y)


    def cmp_to_key(mycmp):
        'Convert a cmp= function into a key= function'

        class K(object):
            def __init__(self, obj, *args):
                self.obj = obj

            def __lt__(self, other):
                return mycmp(self.obj, other.obj) < 0

            def __gt__(self, other):
                return mycmp(self.obj, other.obj) > 0

            def __eq__(self, other):
                return mycmp(self.obj, other.obj) == 0

            def __le__(self, other):
                return mycmp(self.obj, other.obj) <= 0

            def __ge__(self, other):
                return mycmp(self.obj, other.obj) >= 0

            def __ne__(self, other):
                return mycmp(self.obj, other.obj) != 0

        return K
    
    if pl in cache:
        s = cache[pl]
    else:
        cache[pl] = sorted(S, key=cmp_to_key(comp))
        

    print(cache[pl].index(S[k])+1)

Submission status: Time Limit Exceeded

Solution code:
def func(s, di):
    ret = 0
    for i, c in enumerate(s[::-1]):
        if c in di:
            ret += (27 ** i) * di[c]
    return ret

n = input()
ss = [raw_input() for i in range(n)]
q = input()

same_len = max([len(s) for s in ss])
same_len_ss = [s.ljust(same_len, "0") for s in ss]
# print same_len_ss

for i in range(q):
    k, ps = raw_input().split()
    di = {ps[i]: i + 1 for i in range(26)}
    numerized = [func(same_len_s, di) for same_len_s in same_len_ss]
    # print numerized[k - 1]
    print sorted(numerized).index(numerized[int(k) - 1]) + 1

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
import string
N = int(raw_input().strip())
S = []
for n in xrange(0,N):
  Si = raw_input().strip()
  S.append(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)
  p.append(pi)

basep = "abcdefghijklmnopqrstuvwxyz"

def sort_with(pi, queryidx):
  newS = "\n".join(S)
  newS = newS.translate(string.maketrans(pi, basep))
  newS = newS.split()
  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:
S = []
for i in range(int(input())):
    S.append(input())

k = 0
for i in range(int(input())):
    k, pl = input().split()
    p = [i for i in pl]
    k = int(k)-1

    def comp(x, y):
        global p
        if len(x) == 1 and len(y) == 1:
            return p.index(x) - p.index(y)
        for i in range(min(len(x),len(y))):
            if x[i] == y[i]:
                continue
            return p.index(x[i]) - p.index(y[i])
        return min(len(x),len(y)) - len(y)


    def cmp_to_key(mycmp):
        'Convert a cmp= function into a key= function'

        class K(object):
            def __init__(self, obj, *args):
                self.obj = obj

            def __lt__(self, other):
                return mycmp(self.obj, other.obj) < 0

            def __gt__(self, other):
                return mycmp(self.obj, other.obj) > 0

            def __eq__(self, other):
                return mycmp(self.obj, other.obj) == 0

            def __le__(self, other):
                return mycmp(self.obj, other.obj) <= 0

            def __ge__(self, other):
                return mycmp(self.obj, other.obj) >= 0

            def __ne__(self, other):
                return mycmp(self.obj, other.obj) != 0

        return K


    print(sorted(S, key=cmp_to_key(comp)).index(S[k])+1)

Submission status: Time Limit Exceeded

Solution code:
y = None

def cmps(a,b):
    global y
    s = y
    s1 = a
    s2 = b
    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 = []
s_raw = []
for i in xrange(n):
    s_tmp = raw_input()
    s.append(s_tmp)
    s_raw.append(s_tmp)

m = int(raw_input())
for i in xrange(m):
    x, y = raw_input().split()
    x = int(x)
    s.sort(cmp=cmps)
    for j in xrange(len(s)):
        if cmps(s_raw[x-1], s[j]) == 0:
            print j+1
            break

Submission status: Time Limit Exceeded

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)
  newS = "\n".join(S)
  for i in xrange(len(basep)):
    #for j,Si in enumerate(newS):
    #  newS[j] = Si.replace("0"+pi[i], basep[i])
    newS = newS.replace("0"+pi[i], basep[i])
  newS = newS.split()
  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:
ns = int(raw_input())
strings = []

for i in xrange(ns):
    strings.append(raw_input())

nq = int(raw_input())
for i in xrange(nq):
    r = raw_input().split()
    qi = int(r[0])-1
    qo = r[1]

    ss = []
    for i, s in enumerate(strings):
        if i != qi:
            ss.append(s)
    si = strings[qi]

    before = 0

    for i, c in enumerate(si):
        o1 = qo.index(c)

        ssn = []
        for sqi, sq in enumerate(ss):
            if i >= len(sq):
                before += 1
            else:
                o2 = qo.index(sq[i])
                if o1 > o2:
                    before += 1
                if o1 == o2:
                    ssn.append(sq)

        ss = ssn
        if len(ss) == 0:
            break
    print before+1

Submission status: Memory 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)

cost = [[[0]*26 for _ in range(26)] for _ in range(N)]
geta = [0]*N
for k in range(N):
    vn = T.root
    res = 0
    for si in Di[k]:        
        for ti in range(26):
            if si != ti and vn[ti] is not None:
                cost[k][si][ti] += vn[ti].count
        vn = vn[si]
        if vn.end:
            geta[k] += 1

Q = int(readline())
Ans = [None]*Q
for qu in range(Q):
    t, s = readline().strip().split()
    t = int(t) - 1
    s = list(map(lambda x: ord(x)-97, s))
    invs = [None]*26
    for i in range(26):
        invs[s[i]] = i
    res = 0
    for i in range(26):
        for j in range(26):
            if invs[i] > invs[j]:
                res += cost[t][i][j]

    Ans[qu] = res+geta[t]
print('\n'.join(map(str, Ans)))

Submission status: Memory Limit Exceeded

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

N = int(input())
import sys
input = sys.stdin.readline
#S = [[ord(c)-97 for c in input()[:-1]] for _ in range(N)]
S = [input()[:-1] for _ in range(N)]
trie = Trie()
for s in S:
    trie.add(s)
L = [0] + [trie.query(s) for s in S]

Q = int(input())
Ans = []
for _ in range(Q):
    K, P = input().split()
    ans = 0
    P = [ord(c)-97 for c in P]
    L_K = L[int(K)]
    for i, pi in enumerate(P):
        for pj in P[:i]:
            ans += L_K[pi][pj]
        ans += L_K[pi][26]
    Ans.append(ans + 1)
print("\n".join(map(str, Ans)))

Submission status: Memory Limit Exceeded

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

# あとは適当にやったらなんとかなった 1100 点の割には簡単な気がする

class TrieNode:
    def __init__(self):
        self.child = [None] * 27
        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 node.child[c] is None:
                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 enumerate(node.child):
                if child is not None:
                    res_c[i] += child.count
            node = node.child[c]
        return res

N = int(input())
import sys
input = sys.stdin.readline
#S = [[ord(c)-97 for c in input()[:-1]] for _ in range(N)]
S = [input()[:-1] for _ in range(N)]
trie = Trie()
for s in S:
    trie.add(s)
L = [0] + [trie.query(s) for s in S]

Q = int(input())
Ans = []
for _ in range(Q):
    K, P = input().split()
    ans = 0
    P = [ord(c)-97 for c in P]
    L_K = L[int(K)]
    for i, pi in enumerate(P):
        for pj in P[:i]:
            ans += L_K[pi][pj]
        ans += L_K[pi][26]
    Ans.append(ans + 1)
print("\n".join(map(str, Ans)))

Submission status: Memory Limit Exceeded

Solution code:
class TrieNode:
    def __init__(self):
        self.child = [None] * 27
        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:
            if node.child[c] is None:
                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(27)]
        node = self.root
        for c in s:
            res_c = res[c]
            for i, child in enumerate(node.child):
                if child is not None:
                    res_c[i] += child.count
            node = node.child[c]
        return res

N = int(input())
import sys
input = sys.stdin.readline
S = [[ord(c)-97 for c in input()[:-1]] for _ in range(N)]
trie = Trie()
for s in S:
    trie.add(s)
L = [0] + [trie.query(s) for s in S]

Q = int(input())
Ans = []
for _ in range(Q):
    K, P = input().split()
    ans = 0
    P = [ord(c)-97 for c in P]
    L_K = L[int(K)]
    for i, pi in enumerate(P):
        for pj in P[:i]:
            ans += L_K[pi][pj]
        ans += L_K[pi][26]
    Ans.append(ans + 1)
print("\n".join(map(str, Ans)))

Submission status: Memory Limit Exceeded

Solution code:
R=range;T=[0]*28;N=int(input());S=[[ord(C)-95 for C in input()]for _ in[0]*N];U=N*26**2*[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: Memory Limit Exceeded

Solution code:
R=range;T=[0]*28;N=int(input());S=[input()for _ in[0]*N];U=N*26**2*[0];V=N*[0];Q=int(input())
for X in S:
	P=0
	for C in X:
		C=ord(C)-95
		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]:
		C=ord(C)-95
		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: Memory Limit Exceeded

Solution code:
from array import*;R=range;T=array('I',[0]*28);N=int(input());S=[[ord(C)-95 for C in input()]for _ in[0]*N];U=N*26**2*[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+=array('I',[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 X*(A!=C-2):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: Memory Limit Exceeded

Solution code:
R=range;T=[0]*28;N=int(input());S=[tuple(ord(C)-95 for C in input())for _ in[0]*N];U=N*26**2*[0];V=N*[0];Q=int(input())
for X in S:
	P=0
	for C in X:
		if T[P*28+C]==0:T[P*28+C]=len(T)//28;T+=[0]*28
		T[P*28]+=1;P=T[P*28+C]
	T[P*28]+=1;T[P*28+1]=1
for I in R(N):
	P=0
	for C in S[I]:
		for A in R(26):
			X=T[P*28+A+2]
			if X*(A!=C-2):U[676*I+26*A+C-2]+=T[X*28]
		V[I]+=T[P*28+1]
		P=T[P*28+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: Memory Limit Exceeded

Solution code:
R=range;T=[[0]*28];N=int(input());S=[tuple(ord(C)-95 for C in input())for _ in[0]*N];U=N*26**2*[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][0]+=1;P=T[P][C]
	T[P][0]+=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 X*(A!=C-2):U[676*I+26*A+C-2]+=T[X][0]
		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: Memory Limit Exceeded

Solution code:
R=range;T=[[0]*28];N=int(input());S=[[ord(C)-95 for C in input()]for _ in[0]*N];U=N*26**2*[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][0]+=1;P=T[P][C]
	T[P][0]+=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 X*(A!=C-2):U[676*I+26*A+C-2]+=T[X][0]
		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: Memory Limit Exceeded

Solution code:
import array
T=[[0,0,[-1]*26]]
N=int(input())
S=[[ord(C)-97 for C in input()]for _ in[0]*N]
U=N*26**2*[0];V=N*[0]
Q=int(input())
for X in S:
	P=0
	for C in X:
		if T[P][2][C]<0:T[P][2][C]=len(T);T+=[[0,0,array.array('i',[-1]*26)]]
		T[P][0]+=1;P=T[P][2][C]
	T[P][0]+=1;T[P][1]=1
for I in range(N):
	P=0
	for C in S[I]:
		for A in range(26):
			X=T[P][2][A]
			if(X+1)*(A!=C):U[676*I+26*A+C]+=T[X][0]
		V[I]+=T[P][1]
		P=T[P][2][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 range(26):
		for B in range(A+1,26):
			X+=U[676*K+26*P[A]+P[B]]
	print(X);Q-=1

Submission status: Memory Limit Exceeded

Solution code:
N = int(raw_input())
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()

for n in range(N):
    s = raw_input()
    S_list.append(raw_input())
    s_ = ''
    for i in range(len(s)):
        add_node(s_+s[i])
        add_edge(s_, s[i])
        s_ += s[i]
    add_node(s+'0')
    add_edge(s, '0')

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 '0' + alphabed:
            if al == s[i]:
                break
            elif G[s_]['edge'].has_key(al):
                res += G[s_+al]['total']
        s_ += s[i]
    print res + 1