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:
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
import random
class rh:#base,max_n=ありうる文字の最大長,convertを指定すること
    def __init__(self,base,max_n):#baseとmaxnを指定すること。baseは偶数(modが奇数)
        self.mod=random.randrange(1<<54-1,1<<55-1,2)#奇数、衝突させられないよう乱数で生成
        self.base=int(base*0.5+0.5)*2#偶数,英小文字なら26とか
        self.max_n=max_n
        self.pows1=[1]*(max_n+1)
        cur1=1
        for i in range(1,max_n+1):
            cur1=cur1*base%self.mod
            self.pows1[i]=cur1

    def convert(self,c): return alp2num(c,False)#大文字の場合Trueにする
    
    def get(self, s):#特定の文字のhash. O(|s|)
        n=len(s)
        mod=self.mod
        si=[self.convert(ss) for ss in s]
        h1=0
        for i in range(n):h1=(h1+si[i]*self.pows1[n-1-i])%mod
        return h1
    
    def get_roll(self, s, k, uroboros=False):#ローリングハッシュ,sの各文字を始点とした長さkの部分文字のhash値をすべて得る,O(|s|)
        #uroboros: trueの場合文字sを循環させ、n個のハッシュ値を得る。 falseの場合n-k+1個
        n=len(s)
        maxitr=n-k+1
        if uroboros: maxitr=n
    
        si=[self.convert(ss) for ss in s]
        mod=self.mod
        h1=0
        for i in range(k):h1=(h1+si[i%n]*self.pows1[k-1-i])%mod
        hs=[0]*maxitr
        hs[0]=h1
        mbase1=self.pows1[k]
        base=self.base
        
        for i in range(1,maxitr): 
            front=si[i-1];back=si[(i+k-1)%n]
            h1=(h1*base-front*mbase1+back)%mod
            hs[i]=h1
        return hs

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

    N = int(input())
    mod=random.randrange(1<<54-1,1<<55-1,2)
    #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=Counter()
    ans=0
    base=9973
    for im in inds:
        
        s=L[im]

        ls=len(s)
        cur=0
        se=Counter(s)
        #printe(se)
        for i in range(ls):
            for a,val in se.items():
                if val:
                    ai=alp2num(a)
                    ans+=d[(cur*base+ai)%mod]
            si=s[-1-i]
            sin=alp2num(si)
            cur=(cur*base+sin)%mod
            se[si]-=1

        d[cur]+=1

    print(ans)
            





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import re

n = int(input())
count = 0
strings = []

for _ in range(n):
    str = input()
    for existing_str in strings:
        
        # existing_str => strが可能か
        if len(str) == 1:
            regex = "^[a-z]*{}[a-z]*$".format(str)
        else:
            regex = '^[a-z]*' + '[a-z]?'.join(str) + '$'
#         print(regex)
        if re.compile(regex).match(existing_str):
            count += 1
#             print(str, existing_str)
            continue
            
        # string => existing_strが可能か
        if len(existing_str) == 1:
            regex = "^[a-z]*{}[a-z]*$".format(existing_str)
        else:
            regex = '^[a-z]*' + '[a-z]?'.join(existing_str) + '$'
        if re.compile(regex).match(str):
            count += 1
#             print(str, existing_str)
            continue

    strings.append(str)
    
print(count)

Submission status: Wrong Answer

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
    tmp=0
    for i in range(l-1, -1, -1):
        cc = ord(s[i]) - 97
        tmp=26*tmp+cc
        R += d[cc]
        d[cc] = 0
        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: 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()

from collections import defaultdict

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

	for s in A:
		d[s]+=1

	B=[]

	for k,v in d.items():
		B.append([k,v])
	#print(B)

	ans=0

	l=len(B)

	for i in range(l):
		s,v=B[i][0],B[i][1]

		ans+=v*(v-1)//2

		if len(s)==1:
			for ss,vv in B:
				if s!=ss:
					if s in ss:
						ans+=v*vv
		else:
			ls=len(s)
			t=s[:ls-1]
			if i!=l-1:
				for j in range(i+1,l):
					ss,vv=B[j][0],B[j][1]
					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+=v*vv

	print(ans)













































if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque

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() for _ in range(N)]
    S.sort(key=len)
    ans = 0
    for i, s in enumerate(S):
        for j in range(i+1, N):
            if len(s) == 1 and s[0] in S[j]:
                ans += 1
                continue
            elif len(s) == 1:
                continue
            l = len(S)
            last = s[-(l-1):]

            if not S[j].endswith(last):
                continue
            if s[0] in S[j][:-(l-1)]:
                ans += 1
                continue
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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
import random
class rh:#base,max_n=ありうる文字の最大長,convertを指定すること
    def __init__(self,base,max_n):#baseとmaxnを指定すること。baseは偶数(modが奇数)
        self.mod=random.randrange(1<<54-1,1<<55-1,2)#奇数、衝突させられないよう乱数で生成
        self.base=int(base*0.5+0.5)*2#偶数,英小文字なら26とか
        self.max_n=max_n
        self.pows1=[1]*(max_n+1)
        cur1=1
        for i in range(1,max_n+1):
            cur1=cur1*base%self.mod
            self.pows1[i]=cur1

    def convert(self,c): return alp2num(c,False)#大文字の場合Trueにする
    
    def get(self, s):#特定の文字のhash. O(|s|)
        n=len(s)
        mod=self.mod
        si=[self.convert(ss) for ss in s]
        h1=0
        for i in range(n):h1=(h1+si[i]*self.pows1[n-1-i])%mod
        return h1
    
    def get_roll(self, s, k, uroboros=False):#ローリングハッシュ,sの各文字を始点とした長さkの部分文字のhash値をすべて得る,O(|s|)
        #uroboros: trueの場合文字sを循環させ、n個のハッシュ値を得る。 falseの場合n-k+1個
        n=len(s)
        maxitr=n-k+1
        if uroboros: maxitr=n
    
        si=[self.convert(ss) for ss in s]
        mod=self.mod
        h1=0
        for i in range(k):h1=(h1+si[i%n]*self.pows1[k-1-i])%mod
        hs=[0]*maxitr
        hs[0]=h1
        mbase1=self.pows1[k]
        base=self.base
        
        for i in range(1,maxitr): 
            front=si[i-1];back=si[(i+k-1)%n]
            h1=(h1*base-front*mbase1+back)%mod
            hs[i]=h1
        return hs

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

    N = int(input())
    mod=random.randrange(1<<54-1,1<<55-1,2)
    #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=Counter()
    ans=0
    for im in inds:
        
        s=L[im]

        ls=len(s)
        cur=0
        se=Counter(s)
        #printe(se)
        for i in range(ls):
            for a,val in se.items():
                if val:
                    ai=alp2num(a)
                    ans+=d[(cur*26+ai)%mod]

            si=s[-1-i]
            sin=alp2num(si)
            cur=(cur*26+sin)%mod
            se[si]-=1

        d[cur]+=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()

from collections import defaultdict

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

	for s in A:
		d[s]+=1

	B=[]

	for k,v in d.items():
		B.append([k,v])
	#print(B)

	ans=0

	l=len(B)

	for i in range(l):
		s,v=B[i][0],B[i][1]
		if len(s)==1:
			for ss,vv in B:
				if s!=ss:
					if s in ss:
						ans+=v*vv
		else:
			ls=len(s)
			t=s[:ls-1]
			if i!=l-1:
				for j in range(i+1,l):
					ss,vv=B[j][0],B[j][1]
					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+=v*vv

	print(ans)













































if __name__ == "__main__":
	main()

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 range(26):
            c = chr(ord('a')+k)
            if start[c] <= sl-(j+1)-1:
                if s in d.keys():
                    if c in d[s].keys():
                        ans += d[s][c]
        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 range(26):
            c = chr(ord('a')+k)
            if start[c] <= sl-(j+1)-1:
                if s in d.keys():
                    if c in d[s].keys():
                        ans += d[s][c]
        if j == sl-2:
            d[s][S[i][0]] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
a=int(input())
b=[input() for _ in range(a)]
c=0
print(b)
for i in range(a):
    if len(b[i])==1:
        for j in range(i+1,a):
            if b[i] in b[j]:
                c+=1
    else:
        d=0
        while len(b[i])>=2:
            if d%2!=0:
                b[i]=b[i][1:]
                d+=1
                if b[i] in b[i+1:]:
                    c+=1
            else:
                b[i]=b[i][:1]+b[i][2:]
                d+=1
                if b[i] in b[i+1:]:
                    c+=1
print(c)

Submission status: Wrong Answer

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):
		if l == r:
			return 0
		else:
			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()))]
ss.sort(key=lambda x: -len(x))
for s in ss:
	n = len(s)
	rh = RollingHash(s, BASE, MOD)
	suff = rh.get(1, n)
	if suff in d:
		for x in d[suff]:
			if s[0] in x:
				#print(s)
				ans += 1
	alph = set(s[0])
	for i in range(1, n):
		alph.add(s[i])
		tmp = rh.get(i+1, n)
		if tmp in d:
			d[tmp].append(alph)
		else:
			d[tmp] = [alph]
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 range(26):
            c = chr(ord('a')+k)
            if start[c] <= sl-(j+1)-1:
                if c in d[s].keys():
                    ans += d[s][c]
        if j == sl-2:
            d[s][S[i][0]] += 1

print(ans)

Submission status: Wrong Answer

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))
            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]
                    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 in key:
            last = ord(s[-1]) - 97
            h = h1
            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: Wrong Answer

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

N = int(input())
S = [input().rstrip() for _ in range(N)]
S.sort(key=lambda s: -len(s))
dic = {}
dic[-1] = [0] * 26
ans = 0
a = ord('a')
for s in S:
    if len(s) == 1:
        ans += dic[-1][ord(s[0]) - a]
    else:
        h = 0
        for i in range(len(s) - 1, 0, -1):
            h = 26 * h + ord(s[i]) - a
        if h in dic:
            ans += dic[h][ord(s[0]) - a]
    cnt = [0] * 26
    for c in s:
        cnt[ord(c) - a] += 1
    for c in range(26):
        if cnt[c] > 0:
            dic[-1][c] += 1
    h = 0
    for i in range(len(s) - 1, -1, -1):
        h = 26 * h + ord(s[i]) - a
        cnt[ord(s[i]) - a] -= 1
        if h not in dic:
            dic[h] = [0] * 26
        for c in range(26):
            if cnt[c] > 0:
                dic[h][c] += 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 range(26):
            c = chr(ord('a')+k)
            if start[c] <= sl-(j+1)-1:
                ans += d[s][c]
        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 deque

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() for _ in range(N)]
    S.sort(key=len)
    ans = 0
    for i, s in enumerate(S):
        for j in range(i+1, N):
            if len(s) == 1 and s[0] in S[j]:
                ans += 1
                continue
            elif len(s) == 1:
                continue
            l = len(S)
            last = s[-(l-1):]
            if S[j][-(l-1):] != last:
                continue
            if s[0] in S[j][:-(l-1)]:
                ans += 1
                continue
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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]
        first = data_s[0]
        second = data_s[1:]
        size_s = len(data_s)
        size_l = len(data_l)
        if(data_l[size_s*(-1)+1:]== second):
            if(first in data_l[0:size_l-size_s+1]):
                count=count+1

print(count)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque

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() for _ in range(N)]
    S.sort(key=len)
    ans = 0
    for i, s in enumerate(S):
        for j in range(i+1, N):
            if len(s) == 1 and s[0] in S[j]:
                ans += 1
                continue
            elif len(s) == 1:
                continue
            l = len(S)
            last = s[-(l-1):]
            if S[j][-(l-1):] != last:
                continue
            if s[0] in S[j]:
                ans += 1
                continue
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
strs = [input() for _ in range(n)]
counter = 0
for i in range(n):
  for j in range(i):
    if(len(strs[i])<len(strs[j])):
      long_str = strs[j]
      short_str = strs[i]
    else:
      long_str = strs[i]
      short_str = strs[j]
    if len(short_str) == 1 and short_str[0] in long_str:
      counter += 1
    elif short_str[0] in long_str and long_str.endswith(short_str[1:]):
      counter += 1
print(counter)

Submission status: Wrong Answer

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)):
        short = s2[i][1]
        long = s2[j][1]
        short2 = {}
        long2 = {}
        for k in short:
            short2.setdefault((k[0], k[1:]), 0)
            short2[(k[0], k[1:])] += 1
        for k in long:
            temp = s2[j][0] - s2[i][0] + 1
            for l in k[:temp]:
                long2.setdefault((l, k[temp:]), 0)
                long2[(l, k[temp:])] += 1
        for k in short2.keys():
            if k in long2.keys():
                ans += short2[k] * long2[k]
print(ans)