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
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(c):
    return ord(c) - ord("a") + 1

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()
    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 * getc(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:
from collections import defaultdict
def h():
    return [0] * 26

def main():
    N = int(input())
    M = defaultdict(h)
    S = []
    for _ in range(N):
        s = memoryview(bytes(input()[::-1], 'utf-8'))
        S.append(s)
        hs = set()
        for i in reversed(range(len(s))):
            head = s[i] - 97
            hs.add(head)
            for j in hs:
                M[s[:i]][j] += 1
    r = 0
    for s in S:
        r += M[s[:-1]][s[-1] - 97] - 1
    return r

print(main())

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 = "ct"
RTrie = { ctkey: 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 c not in node:
            node[c] = { ctkey: Counter() }
        node = node[c]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#b
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:
from collections import defaultdict
def h():
    return [0] * 26
def c(t):
    return t - 97

def main():
    N = int(input())
    M = defaultdict(h)
    S = []
    for _ in range(N):
        s = memoryview(bytes(input()[::-1], 'utf-8'))
        S.append(s)
        hs = set()
        for i in reversed(range(len(s))):
            head = c(s[i])
            hs.add(head)
            for j in hs:
                M[s[:i]][j] += 1
    r = 0
    for s in S:
        r += M[s[:-1]][c(s[-1])] - 1
    return r

print(main())

Submission status: Time Limit Exceeded

Solution code:
#from sys import *
#Z=stdin.readlines()
N=int(input())
S=[input() for i in range(N)]
X=[[0]*26 for i in range(N)]
for i in range(N-1):
  #S[i]=S[i][:-1]
  S[i]=S[i][::-1]
S[-1]=S[-1][::-1]
F=dict()
for i in range(N):
  for j in range(len(S[i])):
    X[i][ord(S[i][j])-ord('a')]+=1
C=0
D=[]
for i in range(N):
  T=''
  if F.get(T,-1)==-1:
    F[T]=C
    C+=1
    D.append([0]*27)
  for k in range(26):
    if X[i][k]:
      D[F[T]][k]+=1
  for j in range(len(S[i])):
    T=T+S[i][j]
    if F.get(T,-1)==-1:
      F[T]=C
      C+=1
      D.append([0]*27)
    X[i][ord(S[i][j])-ord('a')]-=1
    for k in range(26):
      if X[i][k]:
        D[F[T]][k]+=1
P=0
for i in range(N):
  T=S[i][-1]
  P+=D[F[S[i][:-1]]][ord(T)-ord('a')]-D[F[S[i]]][26]
  D[F[S[i]]][26]+=1
print(P-N)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.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 = [input() for _ in range(int(input()))]
zero = [0 for _ in range(26)]
ss.sort(key=lambda x: -len(x))
for s in ss:
	#print(s)
	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 = set()
		alph.add(ord(s[0])-97)
		for i in range(1, n-1):
			alph.add(ord(s[i])-97)
			tmp = rh.get(i+1, n)
			if tmp in d:
				for x in alph:
					d[tmp][x] += 1
			else:
				d[tmp] = [0 for _ in range(26)]
				for x in alph:
					d[tmp][x] += 1
		alph.add(ord(s[n-1])-97)
		for x in alph:
			zero[x] += 1
	#print(ans)
	#print(d, sep="\n")
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N = NI()
    S = [SI()[::-1] for _ in range(N)]
    S.sort(key=len)
    D = []
    ans = 0
    for s in S:
        s_dict = defaultdict(list)
        for i, t in enumerate(s):
            s_dict[t].append(i)
        D.append(s_dict)

    for i, s in enumerate(S):
        for j in range(i+1, N):
            T = D[j]
            for k, ss in enumerate(s):
                if k != len(s)-1:
                    if k not in T[ss]:
                        break
                else:
                    if T[ss]:
                        if T[ss][-1] >= k:
                            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def func1(str1, str2):
  if str1 == str2:
    return 1
  elif str2 and len(str2) > 1:
    str2_list = []
    for letter in str2:
      str2_list.append(letter)
    str2_pop0 = str2_list
    str2_pop0.pop(0)
    str2_pop0 = ''.join(map(str, str2_pop0))
    result = func1(str1, str2_pop0)
    if result:
      return 1
    str2_list = []
    for letter in str2:
      str2_list.append(letter)
    str2_pop1 = str2_list
    str2_pop1.remove(str2[1])
    if str2_pop1:
      str2_pop1 = ''.join(map(str, str2_pop1))
    result = func1(str1, str2_pop1)
    if result:
      return 1
  else:
    return 0
def func2(str1, str2):
  if str1 == str2:
    return 1
  elif str1 and len(str1) > 1:
    str1_list = []
    for letter in str1:
      str1_list.append(letter)
    str1_pop0 = str1_list
    str1_pop0.pop(0)
    str1_pop0 = ''.join(map(str, str1_pop0))
    result = func2(str1_pop0, str2)
    if result:
      return 1
    str1_list = []
    for letter in str1:
      str1_list.append(letter)
    str1_pop1 = str1_list
    str1_pop1.remove(str1[1])
    if str1_pop1:
      str1_pop1 = ''.join(map(str, str1_pop1))
    result = func2(str1_pop1, str2)
    if result:
      return 1
  else:
    return 0
input_n = input()
N = int(input_n)
a = []
for i in range(N):
  a.append(input())
counter = 0
for i in range(N):
  for j in range(N-i):
    if i != j+i:
      no_match_flag = False
      if len(a[i]) < len(a[j+i]):
        for letter in a[i]:
          if letter not in a[j+i]:
            no_match_flag = True
      else:
        for letter in a[j+i]:
          if letter not in a[i]:
            no_match_flag = True
      if not no_match_flag:
        result = func1(a[i], a[j+i])
        if result:
          counter += 1
        else:
          result = func2(a[i], a[j+i])
          if result:
            counter += 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.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 = [input() for _ in range(int(input()))]
zero = [0 for _ in range(26)]
ss.sort(key=lambda x: -len(x))
for s in ss:
	#print(s)
	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:

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 i in range(N-1) for j in range(i+1, N) if compare(S[i], S[j])]))

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), S))
Ss.sort()

ctkey = "ct"
RTrie = { ctkey: Counter() }
for _, S in Ss:
    charct = Counter(S)
    chars = set(list(S))
    node = RTrie
    L = len(S)
    for i, c in enumerate(S[::-1]):
        if i == L-1:
            ans += node[ctkey][c]
        for a in chars:
            node[ctkey][a] += 1
        charct[c] -= 1
        if charct[c] == 0:
            chars.remove(c)
        if c not in node:
            node[c] = { ctkey: Counter() }
        node = node[c]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
data = []
count = 0
for i in range(n):
    data.append(input())
#print(data)
for i in range(n):
    for j in range(i+1,n):
        if (len(data[i]) <= len(data[j])):
            data_s = data[i]
            data_l = data[j]
        if (len(data[i]) > len(data[j])):
            data_s = data[j]
            data_l = data[i]
        if(len(data_s)==1):
            if(data_s in data_l):
                count += 1
                #print(i, j)
        else:
            if(data_s[1:] == data_l[len(data_s)*(-1)+1:] and data_s[0] in data_l[0:len(data_s)*(-1)+1]):
                count +=1
                #print(i,j)
print(count)

Submission status: Time Limit Exceeded

Solution code:

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

counter = 0
for i in range(N-1):
	for j in range(i+1, N):
		if compare(S[i], S[j]):
			counter += 1
			#print(i, j)
print(counter)

Submission status: Time Limit Exceeded

Solution code:
import re

N = int(input())
S_dict = {}

for _ in range(N):
    s = input()
    S_dict[s] = len(s)

buf = sorted(S_dict.items(), key=lambda x:x[1])

S = [x[0] for x in buf]

ans = 0
for i in range(0, N - 1):
    Si = S[i]
    p = re.compile('[a-z]*' + Si[0] + '[a-z]*' + Si[1:] + '$')
    for j in range(i + 1, N):
        Sj = S[j]
        m = p.match(S[j])
        if m is not None:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def h():
    return [0] * 26
def c(t):
    return ord(t) - ord('a')

def main():
    N = int(input())
    M = defaultdict(h)
    S = []
    for _ in range(N):
        s = input()[::-1]
        S.append(s)
        hs = set()
        for i in reversed(range(len(s))):
            head = c(s[i])
            hs.add(head)
            for j in hs:
                M[s[:i]][j] += 1
    r = 0
    for s in S:
        r += M[s[:-1]][c(s[-1])] - 1
    return r

print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())
S = [input().rstrip() for _ in range(N)]
S.sort(key=lambda s: -len(s))
dic = [defaultdict(int) for _ in range(26)]
cnt1 = [0] * 26
ans = 0
for s in S:
    if len(s) == 1:
        ans += cnt1[ord(s[0]) - ord('a')]
    else:
        ans += dic[ord(s[0]) - ord('a')][s[1:][::-1]]
    cnt = [0] * 26
    for c in s:
        cnt[ord(c) - ord('a')] += 1
    for c in range(26):
        if cnt[c] > 0:
            cnt1[c] += 1
    t = ''
    for i in range(len(s) - 1, -1, -1):
        t += s[i]
        cnt[ord(s[i]) - ord('a')] -= 1
        for c in range(26):
            if cnt[c] > 0:
                dic[c][t] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys;input=sys.stdin.readline
N, = map(int, input().split())
S = []
for _ in range(N):
    s = input().strip()
    S.append(s)
S.sort(key=lambda x:len(x))
D = dict()
dd = set()
R = 0
for s in S:
    l = len(s)
    d = [0]*26
    for c in dd:
        d[c] += 1
    mm = 0
    xs = []
    for i in range(l-1, -1, -1):
        cc = ord(s[i]) - 97
        xs.append(s[i])
        R += d[cc]
        d[cc] = 0
        tmp = "".join(xs)
        if tmp in D:
            for c in D[tmp]:
                d[c] += 1
        if i == 0:
            f = cc
        if i == 1:
            nn = tmp
        mm += 1
    if l != 1:
        if nn not in D:
            D[nn] = set()
        D[nn].add(f)
    else:
        dd.add(f)
print(R)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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)
    d=deque()
    for i in range(l-1):
        d.append(s[i+1])
    for i in range(l-1):
        ki[s[i+1]]=1
        for k in ki:
            d.popleft()
            d.appendleft(k)
            #print(d)
            #moji=[k,s[i+2:]]
            kensa="".join(d)
            #print(kensa)
            if(kensa in data):
                ans+=1
        d.popleft()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=[input()[::-1] for i in range(N)]
X=[[0]*26 for i in range(N)]
D=dict()
for i in range(N):
  for j in range(len(S[i])):
    X[i][ord(S[i][j])-ord('a')]+=1
t=(0,)*26
for i in range(N):
  T=''
  U=list(D.get(T,t))
  for k in range(26):
    if X[i][k]:
      U[k]+=1
  D[T]=tuple(U)
  for j in range(len(S[i])-1):
    T=T+S[i][j]
    X[i][ord(S[i][j])-ord('a')]-=1
    U=list(D.get(T,t))
    for k in range(26):
      if X[i][k]:
        U[k]+=1
    D[T]=tuple(U)
P=0
E=dict()
for i in range(N):
  P+=D[S[i][:-1]][ord(S[i][-1])-ord('a')]-E.get(S[i],0)
  E[S[i]]=E.get(S[i],0+1)
print(P-N)

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=["" for _ in range(N)]
    ll=[0]*N
    for i in range(N):
        s=input()
        ls=len(s)
        ll[i]=ls
        L[i]=s

    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    inds=argsort(ll)
    d=defaultdict(Counter)
    ans=0
    for im in inds:
        s=L[im]

        ls=len(s)
        cur=""
        se=Counter(s)
        #printe(se)
        for i in range(ls):
            for a,val in se.items():
                if val:
                    ans+=d[a][cur]

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

            se[si]-=1
        a=cur[-1]
        d[a][cur[0:-1]]+=1

    print(ans)
            





if __name__ == "__main__":
    main()

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_last = {}
        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_last:
                        dic_last[hh] = [0] * 26
                    for j in range(26):
                        if cnt[i][j] > 0:
                            dic_last[hh][j] += 1
            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_last:
                    ans += dic_last[h][last]
        #print(L, S, ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys;input=sys.stdin.readline
N, = map(int, input().split())
S = []
for _ in range(N):
    s = input().strip()
    S.append(s)
S.sort(key=lambda x:len(x))
D = dict()
dd = set()
R = 0
for s in S:
    l = len(s)
    d = [0]*26
    for c in dd:
        d[c] += 1
    mm = 0
    for i in range(l-1, -1, -1):
        cc = ord(s[i]) - 97
        R += d[cc]
        d[cc] = 0
        if s[i:] in D:
            for c in D[s[i:]]:
                d[c] += 1
        if i == 0:
            f = cc
        mm += 1
    if l != 1:
        if s[1:] not in D:
            D[s[1:]] = set()
        D[s[1:]].add(f)
    else:
        dd.add(f)
print(R)

Submission status: Time Limit Exceeded

Solution code:
import re

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

ans = 0
for i in range(0, N):
    Si = S[i]
    p = re.compile('[a-z]*' + Si[0] + '[a-z]*' + Si[1:] + '$')
    for j in range(0, N):
        if i != j:
            Sj = S[j]
            m = p.match(S[j])
            if m is not None:
                ans += 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=defaultdict(Counter)
    ans=0
    for s in L:
        ls=len(s)
        cur=""
        se=Counter(s)
        #printe(se)
        for i in range(ls):
            for a,val in se.items():
                if val:
                    ans+=d[a][cur]

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

            se[si]-=1
        a=cur[-1]
        d[a][cur[0:-1]]+=1
    
    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 = set(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:
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:
            moji=[k,s[i+2:]]
            kensa="".join(moji)
            #print(kensa)
            if(kensa in data):
                ans+=1

print(ans)

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():
    if len(v)<=1:
      continue
    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:
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:
            moji=[k,s[i+2:]]
            #print("".join(moji))
            if(k+s[i+2:] in data):
                ans+=1

print(ans)