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):
        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():
    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: 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):
        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():
    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: 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 = random.randrange(1<<54-1,1<<55-1,2)
    mod=1<<62-1
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #mod=1000000007
    mod2=999999937

    #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=random.randrange(26,10000,2)

    for im in inds:
        
        s=L[im]

        ls=len(s)
        cur=0
        cur2=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
            #cur2=(cur2*base+sin)%mod2

            se[si]-=1

        d[cur]+=1

    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 = random.randrange(1<<54-1,1<<55-1,2)
    mod=1<<62-1
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #mod=1000000007
    mod2=999999937

    #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=26

    for im in inds:
        
        s=L[im]

        ls=len(s)
        cur=0
        cur2=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
            #cur2=(cur2*base+sin)%mod2

            se[si]-=1

        d[cur]+=1

    print(ans)
            





if __name__ == "__main__":
    main()

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

def Solve(S,exact):
    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

    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,exact)
S=S[::-1]
exact=exact[1:]+[0]
ans+=Solve(S,exact)
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):
        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(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])):
            id=dic[S[i][j]]
            lastappear[i][id]=j

    Sparse=SparseTable(exact)

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

    query=[]
    bit=[BIT(N) for i in range(26)]
    res=0
    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
            R=start+1
            start=-1
            end=i+1
            while end-start>1:
                test=(end+start)//2
                if cond(test,i+1,len(S[i])-1):
                    end=test
                else:
                    start=test
            L=end
            query.append((len(S[i])-1,L,R,dic[S[i][-1]]))
            if L!=i+1:
                res-=1
        for j in range(26):
            if lastappear[i][j]!=-1:
                query.append((lastappear[i][j],N+1,i+1,j))
    start=-1
    end=N-1
    while end-start>1:
        test=(end+start)//2
        if cond(test,N-1,len(S[N-1])-1):
            end=test
        else:
            start=test
    if cond(end,N-1,len(S[N-1])-1):
        query.append((len(S[N-1])-1,end,N-1,dic[S[-1][-1]]))
    query.sort(reverse=True)

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

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])):
            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:
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 = random.randrange(1<<54-1,1<<55-1,2)
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    mod=1000000007
    mod2=999999937

    #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=26

    for im in inds:
        
        s=L[im]

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

            se[si]-=1

        d[(ls,cur)]+=1

    print(ans)
            





if __name__ == "__main__":
    main()