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: Wrong Answer

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):
        t-=1
        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()

def Solve():
    global S
    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])-1,-1,-1):
            id=dic[S[i][j]]
            lastappear[i][id]=j

    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 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))
            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]
ans+=Solve()
print(ans)

Submission status: Wrong Answer

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):
        t-=1
        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])-1,-1,-1):
        id=dic[S[i][j]]
        lastappear[i][id]=j

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

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [input() for i in range(n)]
sorts = sorted(s, key=len)
ans = 0
for i in sorts:
    for j in range(len(i)):
        for k in range(j):
            x = i[k] + i[j:]
            if x in sorts:
                ans += 1
        if i[j] in sorts:
            ans += 1
    ans -= 1
print(ans)

Submission status: Wrong Answer

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
            if len(S[i])-2!=0:
                if S[i][0] in dic_1moji:
                    ans+=1
            if S[i][len(S[i])-1] 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[i][0])        
        else:
            dic[S[i][1:len(S[i])]]=[]
            dic[S[i][1:len(S[i])]].append(S[i][0])


    
print(ans)

Submission status: Wrong Answer

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

_end = -1  #'_'
_count = -2 #'#'
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, {})
      count = current_dict.get(_count, 0) + 1
      current_dict[_count] = count
    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:
  sub_trees = []
  current = trie
  for i in range(len(s)):
    for c in range(ord('a'), ord('z')+1):#'abcdefghijklmnopqrstuvwxyz':
      sub_tree = get_subtree(current, [c])
      ans += get_subtree(sub_tree, s[i:]).get(_count, 0)
      #print(s, i, c, get_subtree(sub_tree, s[i:]), sub_tree)
    current = get_subtree(current, s[i:i+1])
  #print(s, '#', current.get(_count,0), current)
  ans += current.get(_count, 0)

print((ans - N))

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n=II()
	B=[]
	for _ in range(n):
		s=input().rstrip().decode()
		B.append(s[::-1])
	B.sort()
	#print(B)

	ans=0


	l=len(B)

	for i in range(l):
		s=B[i]

		if len(s)==1:
			for ss in B:
				if s!=ss:
					if s in ss:
						ans+=1
		else:
			ls=len(s)
			t=s[:ls-1]
			for j in range(i+1,l):
				ss=B[j]
				if len(ss)<ls:
					break
				elif len(ss)==ls:
					continue
				if t!=ss[:ls-1]:
					break
				else:
					if s[ls-1] in ss[ls-1:]:
						ans+=1

	print(ans)






if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n=II()
	B=[]
	for _ in range(n):
		s=input().rstrip().decode()
		B.append(s[::-1])
	B.sort()
	#print(B)

	ans=0


	l=len(B)

	for i in range(l):
		s=B[i]

		if len(s)==1:
			for ss in B:
				if s!=ss:
					if s in ss:
						ans+=1
		else:
			ls=len(s)
			t=s[:ls-1]
			for j in range(i+1,l):
				ss=B[j]
				if len(ss)<ls:
					break
				elif len(ss)==ls:
					continue
				if t!=ss[:ls-1]:
					break
				else:
					if s[ls-1] in ss[ls-2:]:
						ans+=1

	print(ans)






if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

def main():
    n = int(input())
    s = [None]*n
    system = []
    judge = dict()
    for i in range(n):
        s[i] = "".join(list(reversed(input().replace("\n", ""))))
        if len(s[i]) == 1:
            system.append(s[i])
        else:
            key = dict()
            for j in range(len(s[i])):
                key[s[i][j]] = 1
            for v, k in key.items():
                if v in judge:
                    judge[v] += 1
                else:
                    judge[v] = 1
            
    s.sort()
    ans = 0
    for v in system:
        if v in judge:
            ans += judge[v]
    
    anslist = [0]*(n)
    for i in range(n-1):
        anslist[i] = anslist[i-1]
        key = len(s[i])
        if key == 1:
            continue
        if s[i][:-1] == s[i+1][:key-1]:
            for j in range(key-1, len(s[i+1])):
                if s[i][-1] == s[i+1][j]:
                    ans += anslist[i]+1
                    break
            
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    n = int(input())
    s = [None]*n
    system = []
    judge = dict()
    for i in range(n):
        s[i] = "".join(list(reversed(input().replace("\n", ""))))
        if len(s[i]) == 1:
            system.append(s[i])
        else:
            key = dict()
            for j in range(len(s[i])):
                key[s[i][j]] = 1
            for v, k in key.items():
                if v in judge:
                    judge[v] += 1
                else:
                    judge[v] = 1
            
    s.sort()
    ans = 0
    for v in system:
        if v in judge:
            ans += judge[v]
    
    anslist = [0]*(n)
    for i in range(n-1):
        anslist[i] = anslist[i+1]
        key = len(s[i])
        if key == 1:
            continue
        if s[i][:-1] == s[i+1][:key-1]:
            for j in range(key-1, len(s[i+1])):
                if s[i][-1] == s[i+1][j]:
                    ans += anslist[i]+1
                    break
            
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n=II()
	B=[]
	for _ in range(n):
		s=input().rstrip().decode()
		B.append(s[::-1])
	B.sort()
	#print(B)

	ans=0


	l=len(B)

	for i in range(l):
		s=B[i]

		if len(s)==1:
			for ss in B:
				if s!=ss:
					if s in ss:
						ans+=1
		else:
			ls=len(s)
			t=s[:ls-1]
			if i!=l-1:
				for j in range(i+1,l):
					ss=B[j]
					if len(ss)<ls:
						break
					elif len(ss)==ls:
						continue
					if t!=ss[:ls-1]:
						break
					else:
						if s[ls-1] in ss[ls-2:]:
							ans+=1

	print(ans)






if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

def main():
    n = int(input())
    s = [None]*n
    system = []
    judge = dict()
    for i in range(n):
        s[i] = "".join(list(reversed(input().replace("\n", ""))))
        if len(s[i]) == 1:
            system.append(s[i])
        else:
            key = dict()
            for j in range(len(s[i])):
                key[s[i][j]] = 1
            for v, k in key.items():
                if v in judge:
                    judge[v] += 1
                else:
                    judge[v] = 1
            
    s.sort()
    ans = 0
    for v in system:
        if v in judge:
            ans += judge[v]
    
    for i in range(n-1):
        key = len(s[i])
        if key == 1:
            continue
        if s[i][:-1] == s[i+1][:key-1]:
            for j in range(key-1, len(s[i+1])):
                if s[i][-1] == s[i+1][j]:
                    ans += 1
                    break
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys;input=sys.stdin.readline
N, = map(int, input().split())
MOD=998244353
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
    tmp=0
    for i in range(l-1, -1, -1):
        ee = ord(s[i]) - 97
        tmp = 100*tmp+(ee+1)
        tmp %= MOD
        R += d[ee]
        d[ee] = 0
        if tmp in D:
            for c in D[tmp]:
                d[c] += 1
        if i == 1:
            nn = tmp
    if l != 1:
        if nn not in D:
            D[nn] = set()
        D[nn].add(ee)
    else:
        dd.add(ee)
print(R)

Submission status: Wrong Answer

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):
        t-=1
        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])-1,-1,-1):
        id=dic[S[i][j]]
        lastappear[i][id]=j

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 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))
        id=lastappear[i][dic[alpha]]
        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)

print(ans)

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n=II()
	B=[]
	for _ in range(n):
		s=input().rstrip().decode()
		B.append(s[::-1])
	B.sort()

	ans=0


	l=len(B)

	for i in range(l):
		s=B[i]

		if len(s)==1:
			for ss in B:
				if s!=ss:
					if s in ss:
						ans+=1
		else:
			ls=len(s)
			t=s[:ls-1]
			if i!=l-1:
				for j in range(i+1,l):
					ss=B[j]
					if len(ss)<ls:
						break
					elif len(ss)==ls:
						continue
					if t!=ss[:ls-1]:
						break
					else:
						if s[ls-1] in ss[ls-1:]:
							ans+=1

	print(ans)






if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S = []
for i in range(N):
    S.append(list(input()))

S.sort(key=len)

d = defaultdict(lambda: defaultdict(int))
oned = defaultdict(int) #1文字

ans = 0

for i in range(N):
    s = ''
    sl = len(S[i])
    if sl == 1:
        oned[S[i][0]] += 1
        continue

    # 各文字の最初の場所
    start = defaultdict(int)
    for j in range(sl):
        if start[S[i][j]] == 0:
            start[S[i][j]] = j

    one_flag = defaultdict(int)
    
    for j in range(sl):
        #s += S[i][sl-1-j]
        if oned[S[i][sl-1-j]] == 1 and one_flag[S[i][sl-1-j]] == 0:
            ans += 1
            one_flag[S[i][sl-1-j]] += 1
        #for k in d[s].keys():
        #    if start[k] <= sl-(j+1)-1:
        #        ans += d[s][k]
        if j == sl-2:
            d[s][S[i][0]] += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S = []
for i in range(N):
    S.append(list(input()))

S.sort(key=len)

d = defaultdict(lambda: defaultdict(int))
oned = defaultdict(int) #1文字

ans = 0

for i in range(N):
    s = ''
    sl = len(S[i])
    if sl == 1:
        oned[S[i][0]] += 1
        continue

    # 各文字の最初の場所
    start = defaultdict(int)
    for j in range(sl):
        if start[S[i][j]] == 0:
            start[S[i][j]] = j

    one_flag = defaultdict(int)
    
    for j in range(sl):
        #s += S[i][sl-1-j]
        #if oned[S[i][sl-1-j]] == 1 and one_flag[S[i][sl-1-j]] == 0:
        #    ans += 1
        #    one_flag[S[i][sl-1-j]] += 1
        for k in d[s].keys():
            if start[k] <= sl-(j+1)-1:
                ans += d[s][k]
        if j == sl-2:
            d[s][S[i][0]] += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys;input=sys.stdin.readline
N, = map(int, input().split())
MOD=998244353
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
    tmp=0
    for i in range(l-1, -1, -1):
        ee = ord(s[i]) - 97
        tmp = 100*tmp+ee
        R += d[ee]
        d[ee] = 0
        if tmp in D:
            for c in D[tmp]:
                d[c] += 1
        if i == 1:
            nn = tmp
    if l != 1:
        if nn not in D:
            D[nn] = set()
        D[nn].add(ee)
    else:
        dd.add(ee)
print(R)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S = []
for i in range(N):
    S.append(list(input()))

S.sort(key=len)

d = defaultdict(lambda: defaultdict(int))
oned = defaultdict(int) #1文字

ans = 0

for i in range(N):
    s = ''
    sl = len(S[i])
    if sl == 1:
        oned[S[i][0]] += 1
        continue

    # 各文字の最初の場所
    start = defaultdict(int)
    for j in range(sl):
        if start[S[i][j]] == 0:
            start[S[i][j]] = j

    one_flag = defaultdict(int)
    
    for j in range(sl):
        #s += S[i][sl-1-j]
        if oned[S[i][sl-1-j]] == 1 and one_flag[S[i][sl-1-j]] == 0:
            ans += 1
            one_flag[S[i][sl-1-j]] += 1
        for k in d[s].keys():
            if start[k] <= sl-(j+1)-1:
                ans += d[s][k]
        if j == sl-2:
            d[s][S[i][0]] += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S = []
for i in range(N):
    S.append(list(input()))

S.sort(key=len)

d = defaultdict(lambda: defaultdict(int))
oned = defaultdict(int) #1文字

ans = 0

for i in range(N):
    s = ''
    sl = len(S[i])
    if sl == 1:
        oned[S[i][0]] += 1
        continue

    # 各文字の最初の場所
    start = defaultdict(int)
    for j in range(sl):
        if start[S[i][j]] == 0:
            start[S[i][j]] = j

    one_flag = defaultdict(int)
    """
    for j in range(sl):
        s += S[i][sl-1-j]
        if oned[S[i][sl-1-j]] == 1 and one_flag[S[i][sl-1-j]] == 0:
            ans += 1
            one_flag[S[i][sl-1-j]] += 1
        for k in d[s].keys():
            if start[k] <= sl-(j+1)-1:
                ans += d[s][k]
        if j == sl-2:
            d[s][S[i][0]] += 1
    """
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S = []
for i in range(N):
    S.append(list(input()))

S.sort(key=len)

d = defaultdict(lambda: defaultdict(int))
oned = defaultdict(int) #1文字

ans = 0

for i in range(N):
    s = ''
    sl = len(S[i])
    if sl == 1:
        oned[S[i][0]] += 1
        continue

    # 各文字の最初の場所
    start = defaultdict(int)
    #for j in range(sl):
    #    if start[S[i][j]] == 0:
    #        start[S[i][j]] = j

    one_flag = defaultdict(int)

    for j in range(sl):
        s += S[i][sl-1-j]
        if oned[S[i][sl-1-j]] == 1 and one_flag[S[i][sl-1-j]] == 0:
            ans += 1
            one_flag[S[i][sl-1-j]] += 1
        for k in d[s].keys():
            if start[k] <= sl-(j+1)-1:
                ans += d[s][k]
        if j == sl-2:
            d[s][S[i][0]] += 1
      
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S = []
for i in range(N):
    S.append(list(input()))

S.sort(key=len)

d = defaultdict(lambda: defaultdict(int))
oned = defaultdict(int) #1文字

ans = 0

for i in range(N):
    s = ''
    sl = len(S[i])
    if sl == 1:
        oned[S[i][0]] += 1
        continue

    # 各文字の最初の場所
    start = defaultdict(int)
    for j in range(sl):
        if start[S[i][j]] == 0:
            start[S[i][j]] = j

    one_flag = defaultdict(int)

    for j in range(sl):
        s += S[i][sl-1-j]
        #if oned[S[i][sl-1-j]] == 1 and one_flag[S[i][sl-1-j]] == 0:
        #    ans += 1
        #    one_flag[S[i][sl-1-j]] += 1
        for k in d[s].keys():
            if start[k] <= sl-(j+1)-1:
                ans += d[s][k]
        if j == sl-2:
            d[s][S[i][0]] += 1
      
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S = []
for i in range(N):
    S.append(list(input()))

S.sort(key=len)

d = defaultdict(lambda: defaultdict(int))
oned = defaultdict(int) #1文字

ans = 0

for i in range(N):
    s = ''
    sl = len(S[i])
    if sl == 1:
        oned[S[i][0]] += 1
        continue

    # 各文字の最初の場所
    start = defaultdict(int)
    for j in range(sl):
        if start[S[i][j]] == 0:
            start[S[i][j]] = j

    one_flag = defaultdict(int)

    for j in range(sl):
        s += S[i][sl-1-j]
        if oned[S[i][sl-1-j]] == 1 and one_flag[S[i][sl-1-j]] == 0:
            ans += 1
            one_flag[S[i][sl-1-j]] += 1
        #for k in d[s].keys():
        #    if start[k] <= sl-(j+1)-1:
        #        ans += d[s][k]
        if j == sl-2:
            d[s][S[i][0]] += 1
      
print(ans)