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: Runtime Error

Solution code:
class SparseTable():
    def __init__(self,A):
        N=len(A)
        n=N.bit_length()
        self.table=[[-1 for i in range(n)] for i in range(N)]

        for i in range(N):
            self.table[i][0]=A[i]

        for j in range(1,n):
            for i in range(0,N-2**j+1):
                f=self.table[i][j-1]
                s=self.table[i+2**(j-1)][j-1]
                self.table[i][j]=min(f,s)

    def query(self,s,t):
        b=t-s+1
        m=b.bit_length()-1
        return min(self.table[s][m],self.table[t-2**m+1][m])

class BIT():
    def __init__(self,n):
        self.BIT=[0]*(n+1)
        self.num=n

    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        while idx <= self.num:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
dic={i:e for e,i in enumerate(alphabetlist)}


import sys

input=sys.stdin.readline

N=int(input())
S=[input().rstrip() for i in range(N)]
for i in range(N):
    temp=[S[i][-j-1] for j in range(len(S[i]))]
    S[i]="".join(temp)
S.sort()

exact=[0 for i in range(N)]
for i in range(1,N):
    id=0
    limit=min(len(S[i]),len(S[i-1]))
    while limit>id and S[i][id]==S[i-1][id]:
        id+=1
    exact[i]=id
exact.append(-1)
exact[0]=-1

lastappear=[[-1 for i in range(26)] for j in range(N)]
for i in range(N):
    for j in range(len(S[i])):
        id=dic[S[i][j]]
        lastappear[i][id]=j

def Solve(reverse):
    global S,exact,lastappear
    Sparse=SparseTable(exact)

    def cond(s,n,val):
        if n==N:
            return False
        check=Sparse.query(s,n)
        return check>=val

    def solve(alpha):
        query=[]
        for i in range(N):
            if S[i][-1]==alpha and exact[i+1]>=len(S[i])-1:
                start=i+1
                end=N
                while end-start>1:
                    test=(end+start)//2
                    if cond(i+1,test,len(S[i])-1):
                        start=test
                    else:
                        end=test
                query.append((len(S[i])-1,i+1,start+1))
            id=lastappear[i][dic[alpha]]
            if id!=-1:
                query.append((id,N+1,i+1))
        query.sort(reverse=True)
        res=0
        bit=BIT(N)
        for val,l,r in query:
            if l==N+1:
                bit.update(r,1)
            else:
                res+=bit.query(r)-bit.query(l)
        return res


    ans=0
    for alpha in alphabetlist:
        ans+=solve(alpha)
    return ans

ans=0
ans+=Solve()
S=S[::-1]
exact=exact[::-1]
lastappear=lastappear[::-1]
#ans+=Solve()
print(ans)

Submission status: Runtime Error

Solution code:
class SparseTable():
    def __init__(self,A):
        N=len(A)
        n=N.bit_length()
        self.table=[[-1 for i in range(n)] for i in range(N)]

        for i in range(N):
            self.table[i][0]=A[i]

        for j in range(1,n):
            for i in range(0,N-2**j+1):
                f=self.table[i][j-1]
                s=self.table[i+2**(j-1)][j-1]
                self.table[i][j]=min(f,s)

    def query(self,s,t):
        b=t-s+1
        m=b.bit_length()-1
        return min(self.table[s][m],self.table[t-2**m+1][m])

class BIT():
    def __init__(self,n):
        self.BIT=[0]*(n+1)
        self.num=n

    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        while idx <= self.num:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
dic={i:e for e,i in enumerate(alphabetlist)}


import sys

input=sys.stdin.readline

N=int(input())
S=[input().rstrip() for i in range(N)]
for i in range(N):
    temp=[S[i][-j-1] for j in range(len(S[i]))]
    S[i]="".join(temp)
S.sort()

exact=[0 for i in range(N)]
for i in range(1,N):
    id=0
    limit=min(len(S[i]),len(S[i-1]))
    while limit>id and S[i][id]==S[i-1][id]:
        id+=1
    exact[i]=id

lastappear=[[-1 for i in range(26)] for j in range(N)]
for i in range(N):
    for j in range(len(S[i])):
        id=dic[S[i][j]]
        lastappear[i][id]=j

def Solve():
    global S,exact
    Sparse=SparseTable(exact)

    def cond(s,n,val):
        if n==N:
            return False
        check=Sparse.query(s,n)
        return check>=val

    query=[]
    bit=[BIT(N) for i in range(26)]
    for i in range(N):
        if i!=N-1 and exact[i+1]>=len(S[i])-1:
            start=i+1
            end=N
            while end-start>1:
                test=(end+start)//2
                if cond(i+1,test,len(S[i])-1):
                    start=test
                else:
                    end=test
            query.append((len(S[i])-1,i+1,start+1,dic[S[i][-1]]))
        for j in range(26):
            if lastappear[i][j]!=-1:
                query.append((lastappear[i][j],N+1,i+1,j))
    query.sort(reverse=True)
    res=0
    for val,l,r,id in query:
        if l==N+1:
            bit[id].update(r,1)
        else:
            res+=bit[id].query(r)-bit[id].query(l)
    return res

ans=0
ans+=Solve()
S=S[::-1]
exact=[0]+exact[1::-1]
ans+=Solve()
print(ans)

Submission status: Runtime Error

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

import sys,resource
def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  resource.setrlimit(resource.RLIMIT_STACK, (128*1024*1024,hard))

def dfs(l,k):
    global ans
    #ddprint(f"dfs {k=} {l=} - - - -")
    ll = [[] for i in range(26)]
    x = [0]*26
    for z in l:
        #ddprint(f"lsz {ls[z]} {z=} {k=}")
        c = ord(ls[z][-k-1])-orda
        if len(ls[z])==k+1:
            x[c] += 1
        else:
            ll[c].append(z)
    #ddprint(f"{x=} {ll=}")
    for c in range(26):
        for z in l:
            #if len(ls)==2:
            #    ddprint(f" z1 {z[1]} {k=} {c=} fst {first[z[1]][c]}")
            if first[z][c]>=k and len(ls[z])>k+1:
                ans += x[c]
                #if x[c]>0:
                #    ddprint(f"ans += {x[c]}")
    for c in range(26):
        if len(ll[c])>0:
            dfs(ll[c],k+1)

setrlim()
n = inn()
ls = []
first = [[-1]*26 for i in range(n)]
orda = ord('a')
for i in range(n):
    s = ins()
    ls.append(s)
    for c in range(26):
        p = s.find(chr(orda+c))
        first[i][c] = (len(s)-1-p) if p>=0 else -1
#ddprint(f"{ls=}")
#ddprint(f"{first=}")
ans = 0
dfs(list(range(n)),0)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
S = []
a = ord('a')
for _ in range(N):
  S.append([ord(c) - a for c in input()][::-1])

_end = -1  #'_'
_count = -2 #'#'
def get_count(root):
  if _count in root:
    return root[_count]
  else:
    c = [0] * 26 + [1 if _end in root else 0]
    for k, n in root.items():
      if k not in (_end, _count):
        cc = get_count(n)
        #print(k, cc)
        for i, v in enumerate(cc):
          if i == k:
            c[k] += cc[-1]
          else:
            c[i] += v
    root[_count] = c
    return c
    
def make_trie(words):
  root = dict()
  for word in words:
    current_dict = root
    for letter in word:
      #letter = ord(letter)
      current_dict = current_dict.setdefault(letter, {})
    current_dict[_end] = _end
 
  return root

def get_subtree(trie, word):
  current_dict = trie
  for letter in word:
    #letter = ord(letter)
    if letter not in current_dict:
      return {}
    current_dict = current_dict[letter]
  return current_dict
  
def in_trie(trie, word):
  return _end in get_subtree(trie, word)

trie = make_trie(S)
#print(trie)
#print(get_subtree(trie, 'cy'))
#print(in_trie(trie, 'cy'))
#print(in_trie(trie, 'cyx'))

ans = 0
for s in S:
  count = get_count(get_subtree(trie, s[:-1]))
  #print(s, '#', count[s[-1]], count)
  ans += count[s[-1]]

print((ans - N))

Submission status: Runtime Error

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

import sys,resource
def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  resource.setrlimit(resource.RLIMIT_STACK, (128*1024*1024,hard))

def dfs(ls,k):
    global ans
    #ddprint(f"dfs {k=} {ls=} - - - -")
    ll = [[] for i in range(26)]
    x = [0]*26
    for z in ls:
        c = ord(z[0][-1])-orda
        if len(z[0])==1:
            x[c] += 1
        else:
            ll[c].append((z[0][:-1],z[1]))
    #ddprint(f"{x=} {ll=}")
    for c in range(26):
        for z in ls:
            #if len(ls)==2:
            #    ddprint(f" z1 {z[1]} {k=} {c=} fst {first[z[1]][c]}")
            if first[z[1]][c]>=k and len(z[0])>1:
                ans += x[c]
                #if x[c]>0:
                #    ddprint(f"ans += {x[c]}")
    for c in range(26):
        if len(ll[c])>0:
            dfs(ll[c],k+1)

setrlim()
n = inn()
ls = []
first = [[-1]*26 for i in range(n)]
orda = ord('a')
for i in range(n):
    s = ins()
    ls.append((s,i))
    for c in range(26):
        p = s.find(chr(orda+c))
        first[i][c] = (len(s)-1-p) if p>=0 else -1
#ddprint(f"{ls=}")
#ddprint(f"{first=}")
ans = 0
dfs(ls,0)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
dic = {}
dic_1moji={}

S = [input() for i in range(N)]
S.sort(key=lambda x:len(x))

ans = 0
for i in range(N):
    #今までのものを自分から作れるかどうか
    if len(S[i])!=1:
        if S[i][len(S[i])-2] in dic_1moji:
            ans+=1
    
    chance = {}
    for j in range(len(S[i])-1,-1,-1):
        if S[i][j] in chance:
            ans += chance[S[i][j]]
            chance[S[i][j]]=0
        
        if S[i][j:len(S[i])] in dic:
            for tmp in dic[S[i][j:len(S[i])]]:
                if tmp in chance:
                    chance[tmp]+=1
                else:
                    chance[tmp]=1
        
        

    #自分を辞書に追加
    if len(S[i])==1:
        dic_1moji[S[i]]=1
    else:
        if S[i][1:len(S[i])] in dic:
            dic[S[i][1:len(S[i])]].append(S[0])        
        else:
            dic[S[i][1:len(S[i])]]={}
            dic[S[i][1:len(S[i])]].append(S[0])

    
print(ans)

Submission status: Runtime Error

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)
    if str2_pop0:
    	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

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:
        if len(a[i]) < len(a[j+i]):
          result = func1(a[i], a[j+i])
          if result:
          	counter += 1
        else:
          result = func1(a[j+i], a[i])
          if result:
            counter += 1
print(counter)

Submission status: Runtime Error

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)
    if str2_pop0:
    	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)
    if str1_pop0:
    	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:
        if len(a[i]) < len(a[j+i]):
          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: Runtime Error

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:
        if len(a[i]) < len(a[j+i]):
          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: Runtime Error

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():
    n = getN()
    lis = []
    for i in range(n):
        S = list(getS())
        S.reverse()
        lis.append(S)


    lis.sort(key=lambda x: len(x))
    # 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]
                hakken[c] = 0
            if c in singlec:
                ans += singlec[c]
                singlec[c] = 0

            tmp += base * getc(c)
            tmp %= MOD
            base *= 27
            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[c]

        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: Runtime Error

Solution code:
class SparseTable:
    def __init__(self, a, func=max, one=-10**18):
        self.table = [a[:]]
        self.n = len(a)
        self.logn = self.n.bit_length()
        self.func = func
        self.one = one

        for i in map(lambda x: 1 << x, range(self.logn - 1)):
            self.table.append([])
            for j in range(self.n - i * 2 + 1):
                self.table[-1].append(self.func(self.table[-2][j],
                                                self.table[-2][j + i]))

    def get_section(self, i, j):
        length = j - i
        log = length.bit_length() - 1
        if length <= 0:
            return self.one
        return self.func(self.table[log][i], self.table[log][j - (1 << log)])


n = int(input())
s = []
for i in range(n):
    s.append(input()[::-1])
s.sort()
com = []
for i in range(n-1):
    j = 0
    for x, y in zip(s[i], s[i+1]):
        if x != y:
            break
        j += 1
    com.append(j)

mal = max(map(len, s))

abc = "abcdefghijklmnopqrstuvwxyz"


def cou(ind):
    ret = [[0] * mal]
    for i in range(n):
        ret.append([0] * mal)
        ss = 0
        for j in reversed(range(len(s[i]))):
            ss = max(ss, 1 if s[i][j] == abc[ind] else 0)
            ret[-1][j] = ss

    for i in range(mal):
        for j in range(n):
            ret[j+1][i] += ret[j][i]
    return ret


c_c = [cou(i) for i in range(26)]

sp = SparseTable(com, min, 10**18)

ans = 0
for i in range(n):
    ng = -1
    ok = i
    while abs(ng-ok)>1:
        m = (ng+ok)//2
        if sp.get_section(m,i)>=len(s[i])-1:
            ok = m
        else:
            ng = m
        
    min_ok = ok
    ng = n
    ok = i
    while abs(ng-ok) > 1:
        m = (ng+ok)//2
        if sp.get_section(i,m) >= len(s[i])-1:
            ok = m
        else:
            ng = m
    max_ok = ok

    ch = abc.index(s[i][-1])

    ans += c_c[ch][max_ok+1][len(s[i])-1] - c_c[ch][min_ok][len(s[i])-1]

ans -= n
dic = {}
for i in s:
    if i in dic:
        ans -= dic[i]
        dic[i] += 1
    else:
        dic[i] = 1
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())

ary=[]
for i in range(N):
  ary.append(str( stdin.readline().rstrip() ))

cnt = 0

def compareStr(str1,str2):
  if str1 == str2:
    return True
  elif len(str1)>1:
    if compareStr(str1[0]+str1[2:],str2):
      return True
    elif compareStr(str1[1]+str1[2:],str2):
      return True
    else:
      return False 
  else:
    return False

for i in range(N):
  for j in range(N-i-1):
    if compareStr(ary[i],ary[i+j+1]):
      cnt += 1
    elif compareStr(ary[i+j+1],ary[i]):
      cnt += 1
      
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
Z=sys.stdin.readlines()
N=int(Z[0])
for i in range(N):
  Z[i]=Z[i][:-1]
S=[Z[i+1][::-1] for i in range(N)]
X=[[0]*26 for i in range(N)]
F=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
C=0
D=[]
for i in range(N):
  T=''
  if F.get(T,-1)==-1:
    F[T]=C
    C+=1
    D.append([0]*26)
  for k in range(26):
    if X[i][k]:
      D[F[T]][k]+=1
  for j in range(len(S[i])-1):
    T=T+S[i][j]
    if F.get(T,-1)==-1:
      F[T]=C
      C+=1
      D.append([0]*26)
    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
E=dict()
for i in range(N):
  P+=D[F[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: Runtime Error

Solution code:
import sys
Z=sys.stdin.readlines()
N=int(Z[0])
S=[Z[i+1] 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])-1):
    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]
  S[i]=S[i][:-1]
  P+=D[F[S[i]]][ord(T)-ord('a')]-D[F[S[i]]][26]
  D[F[S[i]]][26]+=1
print(P-N)

Submission status: Runtime Error

Solution code:
from sys import *
Z=stdin.readlines()
N=int(Z[0])
S=[Z[i+1] 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])-1):
    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]
  S[i]=S[i][:-1]
  P+=D[F[S[i]]][ord(T)-ord('a')]-D[F[S[i]]][26]
  D[F[S[i]]][26]+=1
print(P-N)

Submission status: Runtime Error

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:
      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: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, SS):
    from collections import defaultdict
    SS.sort(key=lambda s: -len(s))
    debug(": SS", SS)
    ret = 0
    table = defaultdict(lambda: defaultdict(set))
    shortest = INF
    for i, s in enumerate(SS):
        l = len(s)
        if shortest == INF:
            shortest = l
            table[l][s] = set([i])
        elif shortest == l:
            ret += len(table[l][s])
            table[l][s].add(i)

        elif shortest > l:
            # progress DP
            while shortest > l:
                next = shortest - 1
                for k in table[shortest]:
                    v = table[shortest][k]
                    k1 = k[0] + k[2:]
                    table[next][k1] = table[next][k1].union(v)
                    k2 = k[1:]
                    table[next][k2] = table[next][k2].union(v)
                shortest = next
                debug(": table[next]", table[next])
            ret += len(table[l][s])
            table[l][s].add(i)

        else:
            raise NotImplementedError

    return ret


def main():
    # parse input
    N = int(input())
    SS = []
    for i in range(N):
        SS.append(input().strip().decode('ascii'))
    print(solve(N, SS))


def f(s):
    from collections import deque
    q = deque([s])
    while q:
        x = q.popleft()
        if len(x) > 1:
            q.append(x[0] + x[2:])
            q.append(x[1:])
        print(x)


# tests
T1 = """
3
abcxyx
cyx
abc
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""

T2 = """
6
b
a
abc
c
d
ab
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
5
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Runtime Error

Solution code:
import itertools

n = int(input())
data = [float(input()) for _ in range(n)]

def f(x,y):
    x = x[::-1]
    y = y[::-1]
    buf = 0
    i=0
    while i < len(y):
        if x[i+buf] != y[i]:
            buf+=1
            if buf>1:
                return 0
        else:
            i+=1
    return 1

cnt = 0
for a,b in list(itertools.combinations(data, 2)):
    if len(a) > len(b):
        cnt += f(a,b)
    elif len(a) < len(b):
        cnt += f(b,a)
print(cnt)