Problem:


Score : 700 points

Problem Statement

Limak can repeatedly remove one of the first two characters of a string,
    for example abcxyx \rightarrow acxyx \rightarrow cxyx \rightarrow cyx.

You are given N different strings S_1, S_2, \ldots, S_N.
Among N \cdot (N-1) / 2 pairs (S_i, S_j),
    in how many pairs could Limak obtain one string from the other?

Constraints

2 \leq N \leq 200\,000

S_i consists of lowercase English letters a-z.

S_i \neq S_j

1 \leq |S_i|

|S_1| + |S_2| + \ldots + |S_N| \leq 10^6

Input

Input is given from Standard Input in the following format.

N
S_1
S_2
\vdots
S_N

Output

Print the number of unordered pairs (S_i, S_j)
    where i \neq j and Limak can obtain one string from the other.

Sample Input 1

3
abcxyx
cyx
abc

Sample Output 1

1

The only good pair is (abcxyx, cyx).

Sample Input 2

6
b
a
abc
c
d
ab

Sample Output 2

5

There are five good pairs: (b, abc), (a, abc), (abc, c), (b, ab), (a, ab).



Sample input:
3
abcxyx
cyx
abc


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict,Counter
def saiki(S):
  hitomozi = []
  d = defaultdict(lambda: [])
  cnts = defaultdict(lambda: 0)
  for s in S:
    if len(s)==1:
      hitomozi.append(s)
    else:
      d[s[0]].append(s[1:])
      c = Counter(s)
      for k in c.keys():
        cnts[k] += 1
  for h in hitomozi:
    ans[0] += cnts[h]
  for k,v in d.items():
    saiki(v)

N = int(input())
S = [input()[::-1] for _ in range(N)]
ans = [0]
saiki(S)
print(ans[0])

Submission status: Time Limit Exceeded

Solution code:


ais = [raw_input() for _ in range(int(raw_input()))]
ais.sort(key = len)
import collections
cc = collections.Counter()

def f(w):
	res = set()
	for i in range(len(w)):
		#keep i th
		res.add(w[i])
		for j in range(i+1,len(w)):
			res.add(w[i] + w[j:])
	
	return res

ans = 0
for w in ais:
	for g in f(w):
		ans += cc[g]
	cc[w] +=1
print ans

Submission status: Time Limit Exceeded

Solution code:
import sys;input=sys.stdin.readline
from collections import defaultdict
N, = map(int, input().split())
S = []
for _ in range(N):
    s = input().strip()
    S.append(s)
S.sort(key=lambda x:len(x))
D = defaultdict(set)
R = 0
for s in S:
    l = len(s)
    d = defaultdict(int)
    for c in D[""]:
        d[c] += 1
    for i in range(l-1, -1, -1):
        R += d[s[i]]
        d[s[i]] = 0
        for c in D[s[i:]]:
            d[c] += 1
    D[s[1:]].add(s[0])
print(R)

Submission status: Time Limit Exceeded

Solution code:
mod1 = 1000000007
mod2 = 1000000009
base1 = 2009
base2 = 1007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    S = []
    for _ in range(N):
        s = input().rstrip('\n')
        S.append(s[::-1])

    S.sort(key=lambda s: len(s), reverse=True)
    cnt = []
    for s in S:
        c = [0] * 26
        for ss in s:
            c[ord(ss) - 97] += 1
        cnt.append(c)
    ans = 0
    H1 = [0] * N
    H2 = [0] * N
    for L in range(1, 10**6+1):
        if not S:
            break
        M = len(S)
        key = []
        i = M-1
        dic = {}
        while i >= 0:
            if len(S[i]) == L:
                s = S.pop()
                cnt.pop()
                h1 = H1.pop()
                h2 = H2.pop()
                if L > 1:
                    last = ord(s[L-2]) - 97
                    h1 = (h1 * base1 + last)%mod1
                    h2 = (h2 * base2 + last)%mod2
                key.append((s, h1, h2))
            else:
                if L > 1:
                    ss = ord(S[i][L-2]) - 97
                    cnt[i][ss] -= 1
                    H1[i] = (H1[i] * base1 + ss)%mod1
                    H2[i] = (H2[i] * base2 + ss)%mod2
                    hh = H1[i] << 40 + H2[i]
                    if hh not in dic:
                        dic[hh] = [i]
                    else:
                        dic[hh].append(i)
            i -= 1
        for s, h1, h2 in key:
            last = ord(s[-1]) - 97
            h = h1 << 40 + h2
            if L == 1:
                for i in range(len(cnt)):
                    if cnt[i][last] > 0:
                        ans += 1
            else:
                if h in dic:
                    for i in dic[h]:
                        if cnt[i][last] > 0:
                            ans += 1
        #print(L, S, ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())

ct = {}
for i in range(26):
    c = chr(ord('a')+i)
    ct[c] = Counter()

ans = 0
Ss = []
for _ in range(N):
    S = input()
    Ss.append((-len(S), S))
Ss.sort()

for _, S in Ss:
    chars = set()
    ans += ct[S[0]][S[1:]]
    for i, c in enumerate(S):
        chars.add(c)
        S2 = S[i+1:]
        for a in chars:
            ct[a][S2] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
data={}

for i in range(n):
    s=input()
    data[s]=1

ans=0
for s in data:
    ki={}
    ki[s[0]]=1
    #print(ki)
    l=len(s)
    for i in range(l-1):
        ki[s[i+1]]=1
        for k in ki:
            if(k+s[i+2:] in data):
                ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod1 = 1000000007
mod2 = 1000000009
base1 = 2009
base2 = 1007
eps = 10**-9


def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    N = int(input())
    S = []
    for _ in range(N):
        s = input().rstrip('\n')
        S.append(s[::-1])

    S.sort(key=lambda s: len(s), reverse=True)
    cnt = []
    for s in S:
        c = [0] * 26
        for ss in s:
            c[ord(ss) - 97] += 1
        cnt.append(c)
    ans = 0
    H1 = [0] * N
    H2 = [0] * N
    for L in range(1, 10**6+1):
        if not S:
            break
        M = len(S)
        key = []
        i = M-1
        dic = defaultdict(list)
        while i >= 0:
            if len(S[i]) == L:
                s = S.pop()
                cnt.pop()
                h1 = H1.pop()
                h2 = H2.pop()
                if L > 1:
                    last = ord(s[L-2]) - 97
                    h1 = (h1 * base1 + last)%mod1
                    h2 = (h2 * base2 + last)%mod2
                key.append((s, h1, h2))
            else:
                if L > 1:
                    ss = ord(S[i][L-2]) - 97
                    cnt[i][ss] -= 1
                    H1[i] = (H1[i] * base1 + ss)%mod1
                    H2[i] = (H2[i] * base2 + ss)%mod2
                    dic[H1[i] << 40 + H2[i]].append(i)
            i -= 1
        for s, h1, h2 in key:
            last = ord(s[-1]) - 97
            h = h1 << 40 + h2
            if L == 1:
                for i in range(len(cnt)):
                    if cnt[i][last] > 0:
                        ans += 1
            else:
                if h in dic:
                    for i in dic[h]:
                        if cnt[i][last] > 0:
                            ans += 1
        #print(L, S, ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
sss = [input() for _ in range(n)]
d = {s[1:]: 0 for s in sss}
flags = [1 << (i * 18) for i in range(26)]

for s in sss:
    cnt = Counter(s)
    flag = 0
    for c in cnt:
        flag |= flags[ord(c) - 97]
    if '' in d:
        d[''] += flag
    for i in range(len(s) - 1, 0, -1):
        c = s[i]
        cnt[c] -= 1
        if cnt[c] == 0:
            flag ^= flags[ord(c) - 97]
        if s[i:] in d:
            d[s[i:]] += flag

ans = 0
mask = (1 << 18) - 1
for s in sss:
    cnt = (d[s[1:]] >> ((ord(s[0]) - 97) * 18)) & mask
    ans += cnt - 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod1 = 1000000007
mod2 = 1000000009
base1 = 2009
base2 = 1007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    S = []
    for _ in range(N):
        s = input().rstrip('\n')
        S.append(s[::-1])

    S.sort(key=lambda s: len(s), reverse=True)
    cnt = []
    for s in S:
        c = [0] * 26
        for ss in s:
            c[ord(ss) - 97] += 1
        cnt.append(c)
    ans = 0
    H1 = [0] * N
    H2 = [0] * N
    for L in range(1, 10**6+1):
        if not S:
            break
        M = len(S)
        key = []
        i = M-1
        while i >= 0:
            if len(S[i]) == L:
                s = S.pop()
                cnt.pop()
                h1 = H1.pop()
                h2 = H2.pop()
                if L > 1:
                    last = ord(s[L-2]) - 97
                    h1 = (h1 * base1 + last)%mod1
                    h2 = (h2 * base2 + last)%mod2
                key.append((s, h1, h2))
            else:
                if L > 1:
                    ss = ord(S[i][L-2]) - 97
                    cnt[i][ss] -= 1
                    H1[i] = (H1[i] * base1 + ss)%mod1
                    H2[i] = (H2[i] * base2 + ss)%mod2
            i -= 1
        for s, h1, h2 in key:
            last = ord(s[-1]) - 97
            if L == 1:
                for i in range(len(cnt)):
                    if cnt[i][last] > 0:
                        ans += 1
            else:
                for i in range(len(cnt)):
                    if cnt[i][last] > 0 and H1[i] == h1 and H2[i] == h2:
                        ans += 1
        #print(L, S, ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = {}
for i in range(n):
    temp = input()
    s.setdefault(len(temp), [])
    s[len(temp)].append(temp)
s2 = []
for i, j in s.items():
    s2.append([i, j])
s2.sort()
ans = 0
for i in range(len(s2)):
    for j in range(i + 1, len(s2)):
        for k in s2[i][1]:
            for l in s2[j][1]:
                num = len(k) - 1
                temp1 = l[:len(l) - num]
                temp2 = l[len(l) - num:]
                temp3 = k[:len(k) - num]
                temp4 = k[len(k) - num:]
                if temp3 in temp1 and temp2 == temp4:
                    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())

ct = Counter()
ans = 0
Ss = []
for _ in range(N):
    S = input()
    Ss.append((-len(S), S))

for _, S in sorted(Ss):
    chars = set()
    ans += ct[(S[0], S[1:])]
    for i in range(len(S)):
        c = S[i]
        chars.add(c)
        S2 = S[i+1:]
        for c in chars:
            ct[(c, S2)] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

n = int(input())

strs = [''] * n

ans = 0

for i in range(n):
    strs[i] = input()

for i in range(n):
    for j in range(i + 1, n):
        a = strs[i]
        b = strs[j]

        if len(b) > len(a):
            a, b = b, a

        if len(b) == 1:
            if b in a:
                ans += 1
            continue
        else:
            b_1 = b[0:1]
            b_2 = b[1:]
            a_2 = a[-1 * len(b_2):]
            a_1 = a[:-1 * len(b_2)]

            if a_2 == b_2 and b_1 in a_1:
                ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = []
for i in range(n):
    s.append(input())
r = 0
for i in range(n):
    for j in range(i + 1, n):
        a, b = s[i], s[j]
        if len(a) < len(b): a, b = b, a
        l = len(b) - 1
        if (l == 0 and b in a) or (b[0] in a[:-l] and a[-l:] == b[1:]): r += 1
print(r)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


class TrieNode:
    def __init__(self):
        self.edges = {}
        self.letter___count = Counter()

    def count_strings(self, word):
        curr_node = self
        for letter in word[:-1]:
            if letter not in curr_node.edges:
                return 0
            curr_node = curr_node.edges[letter]
        return curr_node.letter___count[word[-1]]

    def add(self, word):
        curr_node = self
        counts = Counter(word)
        for letter in word:
            for l in counts:
                curr_node.letter___count[l] += 1
            counts[letter] -= 1
            if counts[letter] == 0:
                counts.pop(letter)
            if letter not in curr_node.edges:
                curr_node.edges[letter] = TrieNode()
            curr_node = curr_node.edges[letter]


def main():
    n = int(input())
    strings = sorted([input()[::-1] for _ in range(n)], key=lambda x: -len(x))
    ans = 0
    trie = TrieNode()
    for word in strings:
        ans += trie.count_strings(word)
        trie.add(word)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n = int(readline())
s = read().split()
s.sort(key= lambda x: len(x))

words = dict()
# for si in 'abcdefghijklmnopqrstuvmxyz':
#     words[si] = dict()

ans = 0
for si in s:
    if(len(si)==1):
        head = si[0]
        tail = ''
    else:
        head = si[0]
        tail = si[1:]

    heads = set()
    heads.add(head)
    for i in range(len(tail)+1):
        if( tail[i:] in words):
            tmp = tail[i:]
            for j in heads:
                if(j in words[tmp]):
                    ans += words[tmp][j]
        if(i==len(tail)):
            break
        heads.add(tail[i])

    if(not tail in words):
        words[tail] = dict()
    if(not head in words[tail]):
        words[tail][head] = 1
    else:
        words[tail][head] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    N=int(input())
    L=['']*N
    for i in range(N):
        L[i]=''.join(reversed(list(input())))
    
    L.sort()

    count=0
    for i in range(N):
        k=1
        while True:
            if i+k>=N:
                break

            if L[i][:-1]==L[i+k][:len(L[i])-1]:
                if L[i][-1] in L[i+k][len(L[i])-1:]:
                    count+=1
                k+=1
            else:
                break


        k=1
        while True:
            if i-k==-1:
                break
            if L[i][:-1]==L[i-k][:len(L[i])-1]:
                if L[i][-1] in L[i-k][len(L[i])-1:]:
                    count+=1
                k+=1
            else:
                break

    print(count)

main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = [input() for _ in range(N)]

ans = 0
for i in range(0, N):
    Si = S[i]
    Si_len = len(Si)
    for j in range(0, N):
        if i != j:
            Sj = S[j]
            Sj_len = len(Sj)
            if Sj_len >= Si_len:
                if Si[0] in Sj[:Sj_len - Si_len + 1]:
                    if Si[1:] == Sj[Sj_len - Si_len + 1:]:
                        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
sss = [input() for _ in range(n)]
d = {s[1:]: 0 for s in sss}

for s in sss:
    cnt = Counter(s)
    flag = 0
    for c in cnt:
        k = ord(c) - 97
        flag |= 1 << (k * 20)
    if '' in d:
        d[''] += flag
    for i in range(len(s) - 1, 0, -1):
        c = s[i]
        cnt[c] -= 1
        if cnt[c] == 0:
            flag ^= 1 << ((ord(c) - 97) * 20)
        if s[i:] in d:
            d[s[i:]] += flag

ans = 0
mask = (1 << 20) - 1
for s in sss:
    flag = d[s[1:]]
    bs = ((ord(s[0]) - 97) * 20)
    cnt = (flag >> bs) & mask
    ans += cnt - 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    S = []
    for _ in range(N):
        s = input().rstrip('\n')
        S.append(s[::-1])

    S.sort(key=lambda s: len(s), reverse=True)
    cnt = []
    for s in S:
        c = [0] * 26
        for ss in s:
            c[ord(ss) - 97] += 1
        cnt.append(c)
    ans = 0
    for L in range(1, 10**6+1):
        if not S:
            break
        M = len(S)
        key = []
        i = M-1
        while i >= 0:
            if len(S[i]) == L:
                s = S.pop()
                cnt.pop()
                key.append(s)
            else:
                if L > 1:
                    ss = S[i][L-2]
                    cnt[i][ord(ss) - 97] -= 1
            i -= 1
        for s in key:
            pre = s[:-1]
            last = ord(s[-1]) - 97
            if L == 1:
                for i in range(len(cnt)):
                    if cnt[i][last] > 0:
                        ans += 1
            else:
                for i in range(len(cnt)):
                    if cnt[i][last] > 0 and S[i][:L-1] == pre:
                        ans += 1
        # print(S, L, ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
words = []
ans = 0
for _ in range(N):
    w = list(input())
    w.append(len(w))
    w.reverse()
    words.append(w)
for i,j in itertools.combinations(range(N),2):
    if words[i][0] < words[j][0]:
        i,j = j,i
    for k in range(1,words[j][0]):
        if words[i][k] != words[j][k]:
            break
    else:
        for k in range(words[j][0],words[i][0]+1):
            if words[i][k] == words[j][-1]:
                ans += 1
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    S = [input().rstrip() for i in range(N)]

    from collections import defaultdict
    T = defaultdict(lambda: set())
    for s in S:
        T[len(s)].add(s)

    ans = 0
    for s in S:
        pre = set([s[0]])
        for l in range(len(s)-1, 0, -1):
            pre.add(s[-l])
            if T[l]:
                for p in pre:
                    suf = '' if l==1 else s[-l+1:]
                    if p+suf in T[l]:
                        ans += 1
    print(ans)
solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict

n = int(input())
sss = [input() for _ in range(n)]
d = defaultdict(int)
for s in sss:
    cnt = Counter(s)
    flag = 0
    for c in cnt:
        k = ord(c) - 97
        flag |= 1 << (k * 20)
    d[''] += flag
    for i in range(len(s) - 1, 0, -1):
        c = s[i]
        cnt[c] -= 1
        if cnt[c] == 0:
            flag ^= 1 << ((ord(c) - 97) * 20)
        d[s[i:]] += flag

ans = 0
mask = (1 << 20) - 1
for s in sss:
    flag = d[s[1:]]
    bs = ((ord(s[0]) - 97) * 20)
    cnt = (flag >> bs) & mask
    ans += cnt - 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
mod = 10**23 + 117

d = {}

S = [input()[:-1] for i in range(n)]

S.sort(key = lambda x:len(x))

ans = 0
for s in S:
    if len(s) == 1:
        if -1 in d.keys():
            array = d[-1]
            ans += array[ord(s) - ord("a")]
        else: d[-1] = [0]*26
        d[-1][ord(s) - ord("a")] += 1
    else:
        h = 0
        cnt = [0]*26
        for t in s:
            cnt[ord(t) - ord("a")] += 1
        if -1 in d.keys():
            array = d[-1]
            for i in range(26):
                if cnt[i] > 0 and array[i] > 0:ans += 1
        for t in s[len(s) - 1:0:-1]:
            num = ord(t) - ord("a")
            h += num + 1
            h *= 29
            h %= mod
            cnt[num] -= 1
            if h in d.keys():
                array = d[h]
                for i in range(26):
                    if cnt[i] > 0 and array[i] > 0:ans += 1
        if h not in d.keys(): d[h] = [0]*26
        d[h][ord(s[0]) - ord("a")] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    L = list(input() for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    L.sort(key=lambda k: len(k))
    d=Counter()
    ans=0
    for s in L:
        ls=len(s)
        cur=""
        se=Counter(s)
        #printe(se)
        for i in range(ls):
            
            for a in se:
                if se[a]:
                    ans+=d[cur+a]

            si=s[-1-i]
            cur+=si
            se[si]-=1

        d[cur]+=1
    
    print(ans)
            





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
mod = 10**23 + 117

d = {}

S = [input() for i in range(n)]

S.sort(key = lambda x:len(x))

ans = 0
for s in S:
    if len(s) == 1:
        if -1 in d.keys():
            array = d[-1]
            ans += array[ord(s) - ord("a")]
        else: d[-1] = [0]*26
        d[-1][ord(s) - ord("a")] += 1
    else:
        h = 0
        cnt = [0]*26
        for t in s:
            cnt[ord(t) - ord("a")] += 1
        if -1 in d.keys():
            array = d[-1]
            for i in range(26):
                if cnt[i] > 0 and array[i] > 0:ans += 1
        for t in s[len(s) - 1:0:-1]:
            num = ord(t) - ord("a")
            h += num + 1
            h *= 29
            h %= mod
            cnt[num] -= 1
            if h in d.keys():
                array = d[h]
                for i in range(26):
                    if cnt[i] > 0 and array[i] > 0:ans += 1
        if h not in d.keys(): d[h] = [0]*26
        d[h][ord(s[0]) - ord("a")] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# B

n = int(input())
s_l = [input() for x in range(n)]
s_l.sort(key=len)

ans = 0
for i in range(n):
    _s = s_l[i]
    _l = len(_s)
    if _l == 1:
        tmp_l = [s for s in s_l[i+1:] if ((s.endswith(_s[1:])) and (_s[0] in s))]
        ans += len(tmp_l)
    else:
        tmp_l = [s for s in s_l[i+1:] if ((s.endswith(_s[1:])) and (_s[0] in s[:-(_l-1)]))]
        ans += len(tmp_l)
                
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
Slist = []
for i in range(N):
    S = input()
    Slist.append(S)
Slist.sort(key=len)
dic = defaultdict(lambda:defaultdict(int))
ans = 0
for S in Slist:
    alp = set()
    letter = S
    for i in range(len(S)):
        alp.add(letter[0])
        letter = letter[1:]
        alpdic = dic[letter]
        for X in alpdic.keys():
            if X in alp:
                ans += alpdic[X]
    dic[S[1:]][S[0]] += 1
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
# from collections import defaultdict
ALPHABET_SIZE = 26

def getlist():
	return list(map(int, input().split()))

class Node(object):
	def __init__(self, char):
		self.char = char
		self.children = [-1] * ALPHABET_SIZE
		self.flag = [0] * ALPHABET_SIZE

class Trie(object):
	def __init__(self):
		self.root = Node(' ')

	def _convert_char_to_num(self, char):
		return ord(char) - 97

	def insert(self, word, tail):
		res = 0 #合う値
		current = self.root
		currentFlag = [0] * ALPHABET_SIZE

		for char in word:
			char_index = self._convert_char_to_num(char)
			for i in range(ALPHABET_SIZE):
				currentFlag[i] += current.flag[i]
			res += currentFlag[char_index]
			currentFlag[char_index] = 0

			if current.children[char_index] != -1:
				current = current.children[char_index]

			else:
				new_node = Node(char)
				current.children[char_index] = new_node
				current = new_node

		char_index = self._convert_char_to_num(tail)
		res += currentFlag[char_index]

		current.flag[self._convert_char_to_num(tail)] += 1

		return res


N = int(input())
L = []
for i in range(N):
	S = input()[::-1]
	L.append([len(S), S])

L.sort(key = lambda x:x[0])

ans = 0
trie = Trie()
for val, s in L:
	s1 = s[:-1]
	tail = s[-1]
	ans += trie.insert(s1, tail)
		# print(ans)
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
# from collections import defaultdict
ALPHABET_SIZE = 26

def getlist():
	return list(map(int, input().split()))

class Node(object):
	def __init__(self, char):
		self.char = char
		self.children = [-1] * ALPHABET_SIZE
		self.flag = [0] * ALPHABET_SIZE

class Trie(object):
	def __init__(self):
		self.root = Node(' ')

	def _convert_char_to_num(self, char):
		return ord(char) - 97

	def insert(self, word, tail):
		res = 0 #合う値
		current = self.root
		currentFlag = [0] * ALPHABET_SIZE

		for char in word:
			char_index = self._convert_char_to_num(char)
			for i in range(ALPHABET_SIZE):
				currentFlag[i] += current.flag[i]
			res += currentFlag[char_index]
			currentFlag[char_index] = 0

			if current.children[char_index] != -1:
				current = current.children[char_index]

			else:
				new_node = Node(char)
				current.children[char_index] = new_node
				current = new_node

		char_index = self._convert_char_to_num(tail)
		res += currentFlag[char_index]

		current.flag[self._convert_char_to_num(tail)] += 1

		return res

#処理内容
def main():
	N = int(input())
	L = []
	for i in range(N):
		S = input()[::-1]
		L.append([len(S), S])

	L.sort(key = lambda x:x[0])

	ans = 0
	trie = Trie()
	for val, s in L:
		s1 = s[:-1]
		tail = s[-1]
		ans += trie.insert(s1, tail)
		# print(ans)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Memory Limit Exceeded

Solution code:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
ALPHABET_SIZE = 26

def getlist():
	return list(map(int, input().split()))

class Node(object):
	def __init__(self, char, ALPHABET_SIZE):
		self.char = char
		self.children = [-1] * ALPHABET_SIZE
		self.flag = [0] * ALPHABET_SIZE

class Trie(object):
	def __init__(self):
		self.root = Node(' ', ALPHABET_SIZE)

	def _convert_char_to_num(self, char):
		return ord(char) - ord('a')

	def insert(self, word, tail):
		res = 0 #合う値
		current = self.root
		currentFlag = [0] * ALPHABET_SIZE

		for char in word:
			char_index = self._convert_char_to_num(char)
			for i in range(ALPHABET_SIZE):
				currentFlag[i] += current.flag[i]
			res += currentFlag[char_index]
			currentFlag[char_index] = 0

			if current.children[char_index] != -1:
				current = current.children[char_index]

			else:
				new_node = Node(char, ALPHABET_SIZE)
				current.children[char_index] = new_node
				current = new_node

		char_index = self._convert_char_to_num(tail)
		res += currentFlag[char_index]

		current.flag[self._convert_char_to_num(tail)] += 1

		return res

#処理内容
def main():
	N = int(input())
	L = []
	for i in range(N):
		S = input()[::-1]
		L.append([len(S), S])

	L.sort(key = lambda x:x[0])

	ans = 0
	trie = Trie()
	for val, s in L:
		s1 = s[:-1]
		tail = s[-1]
		ans += trie.insert(s1, tail)
		# print(ans)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Memory Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict,Counter
def saiki(cnts):
  hitomozi = []
  d = defaultdict(lambda: [])
  heads = defaultdict(lambda: 0)
  for s,c in cnts:
    if len(s)==1:
      hitomozi.append(s[0])
    else:
      for k,v in c.items():
        if v>0:
          heads[k] += 1
      t = s[-1]
      c[t] -= 1
      s.pop(-1)
      d[t].append([s,c])
  for h in hitomozi:
    ans[0] += heads[h]
  for v in d.values():
    if len(v)<=1:
      continue
    if len(v)==2:
      s1,c1 = v[0]
      s2,c2 = v[1]
      l1,l2 = len(s1),len(s2)
      if l1==1:
        if l2>1 and c2[s1[0]]>0:
          ans[0] += 1
        continue
      else:
        if l2==1:
          if c1[s2[0]]>0:
            ans[0] += 1
          continue
        elif (l1>l2 and s2==s1[l1-l2:]) or (l2>l1 and s1==s2[l2-l1:]):
          ans[0] += 1
          continue
    saiki(v)
  return 

N = int(input())
S = [list(input()) for _ in range(N)]
ans = [0]
cnts = []
for s in S:
  cnts.append([s,Counter(s)])
saiki(cnts)
print(ans[0])

Submission status: Memory Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict,Counter
def saiki(cnts):
  hitomozi = []
  d = defaultdict(lambda: [])
  heads = defaultdict(lambda: 0)
  for s,c in cnts:
    if len(s)==1:
      hitomozi.append(s[0])
    else:
      for k,v in c.items():
        if v>0:
          heads[k] += 1
      t = s[-1]
      c[t] -= 1
      s.pop(-1)
      d[t].append([s,c])
  for h in hitomozi:
    ans[0] += heads[h]
  for v in d.values():
    if len(v)<=1:
      continue
    saiki(v)
  return 

N = int(input())
S = [list(input()) for _ in range(N)]
ans = [0]
cnts = []
for s in S:
  cnts.append([s,Counter(s)])
saiki(cnts)
print(ans[0])