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**6+5)

class Node:
    def __init__(self):
        self.child = [None] * 26
        self.counts = [0] * 26

    def add(self, s, bucket, idx_s):
        c = s[idx_s]
        if self.child[c] is None:
            self.child[c] = Node()
        for i, cnt in enumerate(bucket):
            if cnt:
                self.counts[i] += 1
        bucket[c] -= 1
        if idx_s >= 1:
            self.child[c].add(s, bucket, idx_s - 1)
        else:
            Leaves.append(self.counts)

    # def get(self, s, idx_s):
    #     c = s[idx_s]
    #     if idx_s > 0:
    #         return self.child[c].get(s, idx_s-1)
    #     else:
    #         return self.counts[c]

Leaves = []
def main():
    trie = Node()
    N = int(input())
    S = [[ord(c)-97 for c in input()] for _ in range(N)]
    for s in S:
        b = [0] * 26
        for c in s:
            b[c] += 1
        trie.add(s, b, len(s)-1)
    ans = -N
    # for s in S:
    #     ans += trie.get(s, len(s)-1)
    for s, l in zip(S, Leaves):
        ans += l[s[0]]
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**6+5)

class Node:
    def __init__(self):
        self.child = {}
        self.counts = defaultdict(int)

    def add(self, s, bucket, idx_s):
        c = s[idx_s]
        if c not in self.child:
            self.child[c] = Node()
        for i, cnt in enumerate(bucket):
            if cnt:
                self.counts[i] += 1
        bucket[c] -= 1
        if idx_s >= 1:
            self.child[c].add(s, bucket, idx_s-1)
        else:
            Leaves.append(self.counts)

    # def get(self, s, idx_s):
    #     c = s[idx_s]
    #     if idx_s > 0:
    #         return self.child[c].get(s, idx_s-1)
    #     else:
    #         return self.counts[c]

Leaves = []
trie = Node()
N = int(input())
S = [[ord(c)-97 for c in input()] for _ in range(N)]
for s in S:
    b = [0] * 26
    for c in s:
        b[c] += 1
    trie.add(s, b, len(s)-1)
ans = -N
# for s in S:
#     ans += trie.get(s, len(s)-1)
for s, l in zip(S, Leaves):
    ans += l[s[0]]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict as dd
N = int(input())

ans = 0
Ss = []
orda = ord('a')
for _ in range(N):
    S = input()
    Ss.append((len(S), list(map(lambda c:ord(c)-orda, S))))
Ss.sort()

ctkey = 26
RTrie = [None]*26 + [0]*26
for i in range(N):
    _, S = Ss.pop()
    charct = Counter(S)
    node = RTrie
    L = len(S)
    for i, c in enumerate(S[::-1]):
        if i == L-1:
            ans += node[ctkey+c]
        for a in charct.keys():
            node[ctkey+a] += 1
        charct[c] -= 1
        if charct[c] == 0:
            charct.pop(c)
        if node[c] is None:
            node[c] = [None]*26 + [0]*26
        node = node[c]

print(ans)

Submission status: Time Limit Exceeded

Solution code:


from itertools import combinations
import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
#N = 1

S = [input() for _ in range(N)]


def compare(a, b):
	if len(a)>len(b):
		longer = a
		shorter = b
	else:
		longer = b
		shorter = a
	if len(shorter)<2:
		return shorter in longer
	return longer.endswith(shorter[1:]) and shorter[0] in longer[:1-len(shorter)]

print(len([None for a, b in combinations(S, 2) if compare(a, b)]))

Submission status: Time Limit Exceeded

Solution code:
# from heapq import heapify, heappop, heappush
from bisect import bisect_left, bisect_right
# from collections import defaultdict
# import sys
# input = lambda: sys.stdin.readline().rstrip()
# sys.setrecursionlimit(10**9)
# MOD = 10**9 + 7

# Copyright (c) 2012 Hiroshi Manabe (manabe.hiroshi@gmail.com)
# Based on wat-array (2010 Daisuke Okanohara)
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
#
# 1. Redistributions of source code must retain the above Copyright
#    notice, this list of conditions and the following disclaimer.
#
# 2. Redistributions in binary form must reproduce the above Copyright
#    notice, this list of conditions and the following disclaimer in the
#    documentation and/or other materials provided with the distribution.
#
# 3. Neither the name of the authors nor the names of its contributors
#    may be used to endorse or promote products derived from this
#    software without specific prior written permission.
#
#from bit_vector_mock import BitVectorMock
class BitVectorMock(object):
    def __init__(self, size):
        self._bytearray = bytearray(size + 7 / 8)
        self._bit_len = size

    def Set(self, pos, bit):
        if pos >= self._bit_len:
            raise ValueError

        if bit not in (0, 1):
            raise ValueError

        self._bytearray[pos / 8] |= bit << (pos % 8)

    def Peek(self, pos):
        if pos < 0 or pos >= self._bit_len:
            raise ValueError

        return 1 if (self._bytearray[(pos / 8)] & (1 << pos % 8)) else 0

    def GetLength(self):
        return self._bit_len

    def Rank(self, bit, pos):
        if bit not in (0, 1):
            raise ValueError

        if pos < 0:
            raise ValueError

        rank = 0

        for i in range(pos):
            if self.Peek(i) == bit:
                rank += 1

        return rank

    def Select(self, bit, rank):
        if bit not in (0, 1):
            raise ValueError

        if rank <= 0:
            return -1

        pos = 0

        r = 0
        for i in range(self._bit_len):
            if self.Peek(i) == bit:
                r += 1
                if rank == r:
                    return i + 1

        return -1

class WaveletMatrix(object):
    def __init__(self, bits, array, create_cache=True):
        def get_reversed_first_bits(num, max_bit, bit_num, bit_reverse_table):
            return bit_reverse_table[num & ((1 << max_bit) -
                                            (1 << (max_bit - bit_num)))]

        if bits < 0:
            raise ValueError

        self._bits = bits

        max_value = 1 << bits

        self._has_cache = create_cache
        if create_cache:
            self._bit_reverse_table = []

            for i in range(max_value):
                rev = 0
                for j in range(bits):
                    rev |= ((i & (1 << j)) >> j) << (bits - j - 1)

                self._bit_reverse_table.append(rev)

        for n in array:
            if n >= max_value:
                raise ValueError

        self._length = len(array)

        cur_array = array
        self._wavelet_matrix = []
        self._zero_counts = []

        if create_cache:
            self._node_begin_pos = []
            prev_begin_pos = [0, self._length]

            for i in range(bits):
                self._wavelet_matrix.append(BitVectorMock(self._length))
                self._node_begin_pos.append([0] * ((1 << (i+1)) + 1))

                for n in array:
                    bit = 1 if (n & (1 << bits - i - 1)) else 0
                    subscript = get_reversed_first_bits(n, bits, i,
                                                        self._bit_reverse_table)
                    self._wavelet_matrix[i].Set(prev_begin_pos[subscript], bit)
                    prev_begin_pos[subscript] += 1
                    self._node_begin_pos[i][subscript + (bit << i) + 1] += 1

                for n in reversed(range(1 << i)):
                    prev_begin_pos[n+1] = prev_begin_pos[n]

                prev_begin_pos[0] = 0

                for j in range(1 << (i+1)):
                    self._node_begin_pos[i][j+1] += self._node_begin_pos[i][j]

                self._zero_counts.append(self._node_begin_pos[i][1 << i])

                prev_begin_pos = self._node_begin_pos[i]

        else:
            for i in range(bits):
                test_bit = 1 << (bits - i - 1)
                next_array = [[], []]
                self._wavelet_matrix.append(BitVectorMock(len(array)))

                for j in range(len(cur_array)):
                    n = cur_array[j]
                    bit = 1 if (n & test_bit) else 0
                    self._wavelet_matrix[i].Set(j, bit)
                    next_array[bit].append(n)

                self._zero_counts.append(len(next_array[0]))

                cur_array = next_array[0] + next_array[1]


    def Access(self, pos):
        if pos < 0 or pos >= self._length:
            raise ValueError

        index = pos
        num = 0

        for i in range(self._bits):
            bit = self._wavelet_matrix[i].Peek(index)
            num <<= 1
            num |= bit

            index = self._wavelet_matrix[i].Rank(bit, index)

            if bit:
                index += self._zero_counts[i]

        return num

    def Rank(self, num, pos):
        (less, more, rank) = self.RankAll(num, 0, pos)
        return rank

    def RankLessThan(self, num, pos):
        (less, more, rank) = self.RankAll(num, 0, pos)
        return less

    def RankMoreThan(self, num, pos):
        (less, more, rank) = self.RankAll(num, 0, pos)
        return more

    def RankAll(self, num, begin_pos, end_pos):
        if num < 0 or num >= (1 << self._bits):
            raise ValueError

        if (begin_pos < 0 or begin_pos > self._length or
            end_pos < 0 or end_pos > self._length):
            raise ValueError

        if begin_pos >= end_pos:
            return (0, 0, 0)

        more_and_less = [0, 0]
        node_num = 0

        from_zero = True if begin_pos == 0  and self._has_cache else False
        to_end = True if end_pos == self._length and self._has_cache else False

        for i in range(self._bits):
            bit = 1 if num & (1 << (self._bits - i - 1)) else 0
            range_bits = end_pos - begin_pos

            if from_zero:
                begin_zero = self._node_begin_pos[i][node_num]
            else:
                begin_zero =  self._wavelet_matrix[i].Rank(0, begin_pos)

            if to_end:
                end_zero = self._node_begin_pos[i][node_num+1]
            else:
                end_zero = self._wavelet_matrix[i].Rank(0, end_pos)

            if bit:
                begin_pos += self._zero_counts[i] - begin_zero
                end_pos += self._zero_counts[i] - end_zero
            else:
                begin_pos = begin_zero
                end_pos = end_zero

            non_match_bits = range_bits - (end_pos - begin_pos)
            node_num |= bit << i
            more_and_less[bit] += non_match_bits

        return (more_and_less[1], more_and_less[0],
                end_pos - begin_pos)

    def Select(self, num, rank):
        return self.SelectFromPos(num, 0, rank)

    def SelectFromPos(self, num, pos, rank):
        if num < 0 or num >= (1 << self._bits):
            raise ValueError

        if rank <= 0:
            raise ValueError

        if pos < 0 or pos >= self._length:
            raise ValueError

        if pos == 0 and self._has_cache:
            num_rev = self._bit_reverse_table[num]
            index = self._node_begin_pos[-1][num_rev] 
        else:
            index = pos
            for i in range(self._bits):
                bit = 1 if  num & (1 << (self._bits - i - 1)) else 0
                index = self._wavelet_matrix[i].Rank(bit, index)

                if bit:
                    index += self._zero_counts[i]

        index += rank

        for i in reversed(range(self._bits)):
            bit = 1 if num & (1 << (self._bits - i - 1)) else 0

            if bit:
                index -= self._zero_counts[i]

            index = self._wavelet_matrix[i].Select(bit, index)

            if index == -1:
                return -1

        return index

    def QuantileRange(self, begin_pos, end_pos, k):
        if (begin_pos < 0 or begin_pos > self._length
            or end_pos < 0 or end_pos > self._length):
            raise ValueError

        if k < 0 or k >= end_pos - begin_pos:
            raise ValueError

        orig_begin_pos = begin_pos
        num = 0
        from_zero = True if begin_pos == 0 and self._has_cache else False
        to_end = True if end_pos == self._length and self._has_cache else False
        node_num = 0

        for i in range(self._bits):
            if from_zero:
                begin_zero = self._node_begin_pos[i][node_num]
            else:
                begin_zero = self._wavelet_matrix[i].Rank(0, begin_pos)

            if to_end:
                end_zero = self._node_begin_pos[i][node_num+1]
            else:
                end_zero = self._wavelet_matrix[i].Rank(0, end_pos)

            zero_bits = end_zero - begin_zero

            bit = 0 if k < zero_bits else 1

            if bit:
                k -= zero_bits
                begin_pos += self._zero_counts[i] - begin_zero
                end_pos += self._zero_counts[i] - end_zero
            else:
                begin_pos = begin_zero
                end_pos = end_zero

            node_num |= bit << i
            num <<= 1
            num |= bit

        if self._has_cache:
            return (num, self.Select(
                    num, begin_pos + k -
                    self._node_begin_pos[-1][
                        self._bit_reverse_table[num]] + 1) - 1)
        else:
            return (num, self.SelectFromPos(num, orig_begin_pos, k + 1) - 1)

inpl = lambda: list(map(int,input().split()))
N = int(input())
S = [input()[::-1] for _ in range(N)]
S.sort(key = lambda x: x[:-1])

lastletter = [[-1]*N for _ in range(26)]
for i in range(N):
    s = S[i]
    for n in range(len(s)):
        c = s[n]
        lastletter[ord(c) - ord('a')][i] = n

wm = [WaveletMatrix(32,lastletter[q]) for q in range(26)]

ans = 0
for i in range(N):
    s = S[i]
    L = len(s)
    key = s[:-1]
    v = s[-1]
    p = bisect_left(S, key)
    q = bisect_right(S, key)
    for j in range(p,q):
        if j == i:
            continue
        t = S[j]
        ans += wm[ord(v)-ord('a')].RankAll(L-1,p,q)[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

BASE, MOD = 1999849216943526259, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			# case of letters
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

	# [l. r)
	def get(self, l, r):
		return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

d = dict()
ans = 0
ss = [str(input())[2:-1] for _ in range(int(input()))]
zero = [0 for _ in range(26)]
ss.sort(key=lambda x: -len(x))
for s in ss:
	n = len(s)
	rh = RollingHash(s, BASE, MOD)
	if n == 1:
		ans += zero[ord(s[0])-97]
	else:
		suff = rh.get(1, n)
		if suff in d:
			ans += d[suff][ord(s[0])-97]
		alph = [0 for _ in range(26)]
		alph[ord(s[0])-97] = 1
		for i in range(1, n-1):
			alph[ord(s[i])-97] = 1
			tmp = rh.get(i+1, n)
			if tmp in d:
				for i, a in enumerate(alph):
					d[tmp][i] += a
			else:
				d[tmp] = [0 for _ in range(26)]
				for i, a in enumerate(alph):
					d[tmp][i] += a
		alph[ord(s[n-1])-97] = 1
		for i, a in enumerate(alph):
			zero[i] += a
	#print(ans)
	#print(d, sep="\n")
print(ans)

Submission status: Time Limit Exceeded

Solution code:


from itertools import combinations


N = int(input())
#N = 1

S = [input() for _ in range(N)]


def compare(a, b):
	if len(a)>len(b):
		longer = a
		shorter = b
	else:
		longer = b
		shorter = a
	if len(shorter)<2:
		return shorter in longer
	return longer.endswith(shorter[1:]) and shorter[0] in longer[:1-len(shorter)]

print(len([None for a, b in combinations(S, 2) if compare(a, b)]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**6+5)

class Node:
    def __init__(self):
        self.child = {}
        self.counts = defaultdict(int)

    def add(self, s, bucket, idx_s):
        c = s[idx_s]
        if c not in self.child:
            self.child[c] = Node()
        for i, cnt in enumerate(bucket):
            if cnt:
                self.counts[i] += 1
        bucket[c] -= 1
        if idx_s >= 1:
            self.child[c].add(s, bucket, idx_s-1)

    def get(self, s, idx_s):
        c = s[idx_s]
        if idx_s > 0:
            return self.child[c].get(s, idx_s-1)
        else:
            return self.counts[c]

trie = Node()
N = int(input())
S = [[ord(c)-97 for c in input()] for _ in range(N)]
for s in S:
    b = [0] * 26
    for c in s:
        b[c] += 1
    trie.add(s, b, len(s)-1)
ans = -N
for s in S:
    ans += trie.get(s, len(s)-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#b
import sys
def input(): return sys.stdin.readline().strip()
n = int(input())
s = [input() for _ in range(n)]
s.sort(key=len)
ans = 0
trie = {'!': True}
for si in s:
    cursor = trie
    si = list(si)
    while True:
        for nextchar in cursor:
            if nextchar == '!':
                continue
            if '!' in cursor[nextchar] and nextchar in si:
                ans += 1
        popchar = si.pop(-1)
        if popchar in cursor:
            cursor = cursor[popchar]
        else:
            cursor[popchar] = {}
            cursor = cursor[popchar]
            for popchar in reversed(si):
                cursor[popchar] = {}
                cursor = cursor[popchar]
            cursor['!'] = True
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6+5)

class Node:
    def __init__(self):
        self.child = [None] * 26
        self.counts = [0] * 26

    def add(self, s, bucket, idx_s):
        c = s[idx_s]
        if self.child[c] is None:
            self.child[c] = Node()
        for i, cnt in enumerate(bucket):
            if cnt:
                self.counts[i] += 1
        bucket[c] -= 1
        if idx_s >= 1:
            self.child[c].add(s, bucket, idx_s-1)

    def get(self, s, idx_s):
        c = s[idx_s]
        if idx_s > 0:
            return self.child[c].get(s, idx_s-1)
        else:
            return self.counts[c]

trie = Node()
N = int(input())
S = [[ord(c)-97 for c in input()] for _ in range(N)]
for s in S:
    b = [0] * 26
    for c in s:
        b[c] += 1
    trie.add(s, b, len(s)-1)
ans = -N
for s in S:
    ans += trie.get(s, len(s)-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

BASE, MOD = 80408696819889532, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			# case of letters
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

	# [l. r)
	def get(self, l, r):
		return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

d = dict()
ans = 0
ss = [str(input())[2:-1] for _ in range(int(input()))]
zero = [0 for _ in range(26)]
ss.sort(key=lambda x: -len(x))
for s in ss:
	n = len(s)
	rh = RollingHash(s, BASE, MOD)
	if n == 1:
		ans += zero[ord(s[0])-97]
	else:
		suff = rh.get(1, n)
		if suff in d:
			ans += d[suff][ord(s[0])-97]
		alph = [0 for _ in range(26)]
		alph[ord(s[0])-97] = 1
		for i in range(1, n-1):
			alph[ord(s[i])-97] = 1
			tmp = rh.get(i+1, n)
			if tmp in d:
				for i, a in enumerate(alph):
					d[tmp][i] += a
			else:
				d[tmp] = [0 for _ in range(26)]
				for i, a in enumerate(alph):
					d[tmp][i] += a
		alph[ord(s[n-1])-97] = 1
		for i, a in enumerate(alph):
			zero[i] += a
	#print(ans)
	#print(d, sep="\n")
print(ans)

Submission status: Time Limit Exceeded

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

def solve():
    ordA = ord('a')

    N = int(input())
    Sss = [input().rstrip() for _ in range(N)]

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

    fsss = []
    Ass = []
    for Ss in Sss:
        As = [ord(S)-ordA for S in Ss[::-1]]
        Ass.append(As)
        fss = []
        fs = [0] * 26
        for i in reversed(range(len(As))):
            fs[As[i]] = 1
            fss.append(fs[:])
        fsss.append(fss[::-1])

    ans = 0
    nodes = []
    nodes.append([-1]*26)
    nums = []
    nums.append([0]*26)
    numNode = 1
    for As, fss in zip(Ass, fsss):
        lenA = len(As)
        iNode = 0
        for j in range(lenA):
            A = As[j]
            fs = fss[j]
            for c in range(26):
                if fs[c]:
                    ans += nums[iNode][c]

            if nodes[iNode][A] == -1:
                nodes.append([-1]*26)
                nums.append([0]*26)
                nodes[iNode][A] = numNode
                numNode += 1
            else:
                pass

            if j == lenA-1:
                nums[iNode][As[-1]] += 1

            iNode = nodes[iNode][A]

    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict as dd
N = int(input())

ans = 0
Ss = []
orda = ord('a')
for _ in range(N):
    S = input()
    Ss.append((-len(S), list(map(lambda c:ord(c)-orda, S))))
Ss.sort()

ctkey = 26
RTrie = [None]*26 + [0]*26
for _, S in Ss:
    charct = Counter(S)
    node = RTrie
    L = len(S)
    for i, c in enumerate(S[::-1]):
        if i == L-1:
            ans += node[ctkey+c]
        for a in charct.keys():
            node[ctkey+a] += 1
        charct[c] -= 1
        if charct[c] == 0:
            charct.pop(c)
        if node[c] is None:
            node[c] = [None]*26 + [0]*26
        node = node[c]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        # self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        # for i in range(1, self.h+1):
        #     for j in range(1, self.w+1):
        #         cx, cy = j, i
        #         for dx, dy in move_eight:
        #             nx, ny = dx + cx, dy + cy
def getc():
    a = ord("a")
    ret = dict()
    for i in range(1, 27):
        ret[chr(a - 1 + i)] = i
    # print(ret)
    return ret

def solve():
    MOD = 67280421310721
    n = getN()
    lis = []
    for i in range(n):
        S = list(getS())
        S.reverse()
        lis.append(S)


    lis.sort(key=lambda x: len(x))
    # lis.sort()
    # print(lis)
    ans = 0
    single = dict()
    hash = dict()
    cd = getc()
    for s in lis:
        if len(s) == 1:
            single[s[0]] = 1
            continue
        base = 27
        tmp = 0
        hakken = defaultdict(int)
        singlec = copy.deepcopy(single)
        for c in s[:-1]:
            if c in hakken:
                ans += hakken[c]
                del hakken[c]
            if c in singlec:
                ans += singlec[c]
                del singlec[c]

            tmp = tmp + (base * cd[c]) % MOD
            # tmp %= MOD
            base = (base * 27) % MOD
            # base %= MOD
            if tmp in hash:
                for tgt in hash[tmp]:
                    hakken[tgt] += 1


        if s[-1] in hakken:
            ans += hakken[s[-1]]
        if s[-1] in singlec:
            ans +=singlec[s[-1]]

        if tmp in hash:
            hash[tmp].append(s[-1])
        else:
            hash[tmp] = [s[-1]]
        # print(ans, s, single)

    print(ans)







def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Time Limit Exceeded

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

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

base = ord('a')
s = [[] for _ in range(n)]
for i,si in enumerate(data):
    num = 0
    for ch in si:
        s[i].append(ord(ch)-base+1)

s_tails = [[] for _ in range(n)]
for i,si in enumerate(s):
    s_tails[i].append(0)
    now = 0
    for j,si_j in enumerate(si[1:][::-1]):
        now += si_j * pow(27,j)
        s_tails[i].append(now)

words = dict()

ans = 0
for si,s_tail in zip(s,s_tails):
    head = si[0]

    heads = set()
    heads.add(head)

    for i,num in enumerate(s_tail[::-1],1):
        if( num in words):
            word = words[num]
            for j in heads:
                if(j in word):
                    ans += word[j]
        if(i==len(si)):
            break
        heads.add(si[i])

    if(not s_tail[-1] in words):
        words[s_tail[-1]] = dict()

    if(not head in words[s_tail[-1]]):
        words[s_tail[-1]][head] = 1
    else:
        words[s_tail[-1]][head] += 1

    # print(si,ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict as dd
N = int(input())

ans = 0
Ss = []
for _ in range(N):
    S = input()
    Ss.append((-len(S), list(map(lambda c:ord(c)-ord('a'), S))))
Ss.sort()

ctkey = 26
RTrie = [None]*26 + [Counter()]
for _, S in Ss:
    charct = Counter(S)
    node = RTrie
    L = len(S)
    for i, c in enumerate(S[::-1]):
        if i == L-1:
            ans += node[ctkey][c]
        for a in charct.keys():
            node[ctkey][a] += 1
        charct[c] -= 1
        if charct[c] == 0:
            charct.pop(c)
        if node[c] is None:
            node[c] = [None]*26 + [Counter()]
        node = node[c]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import string

N = int(input())
words = []

for _ in range(N):
    words.append(input())

def char_to_i(c):
    return string.ascii_letters.index(c) % 26

class Node:
    def __init__(self):
        self.children = [None for _ in range(26)]
        self.count = 0

    def append(self, word):
        i = char_to_i(word[0])
        if self.children[i] is None:
            self.children[i] = Node()

        if len(word) == 1:
            self.children[i].count += 1
            return 
        else:
            self.children[i].append(word[1:])

    def exists(self, word):
        i = char_to_i(word[0])
        if self.children[i] is None:
            return 0
    
        # case exist i
        if len(word) == 1:
            return self.children[i].count
        else:
            return self.children[i].exists(word[1:])



def remac(word):
    if len(word) == 1:
        return []
    if len(word) == 2:
        return [word[1], word[0]]
    
    return [word[1:], word[0]+word[2:]]


def extract(word):
    candidates = {}
    queue = []
    queue.append(word)
    
    while len(queue) > 0:
        c = queue.pop()
        candidates[c] = ""
        queue.extend(remac(c))
    
    return candidates.keys()


len_sorted_words = sorted(words, key=lambda x: len(x), reverse=True)

results = 0
node = Node()
for word in len_sorted_words:
    # check exists
    exist_count = node.exists(word)
    results += exist_count

    # append search target
    candidates = extract(word)
    for candidate in candidates:
        node.append(candidate)

print(results)