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

Solution code:
class Trie:
    class Node:
        def __init__(self,c):
            self.c=c
            self.next_c_id={}
            #self.common=0
            self.end=-1

    def __init__(self):
        self.trie=[self.Node('')]
    
    def add(self,id,s):
        i=0
        now=0
        ary=[0]
        while i<len(s) and s[i] in self.trie[now].next_c_id:
            now=self.trie[now].next_c_id[s[i]]
            ary.append(now)
            #self.trie[now].common+=1
            i+=1
        while i<len(s):
            self.trie[now].next_c_id[s[i]]=len(self.trie)
            now=len(self.trie)
            ary.append(now)
            self.trie.append(self.Node(s[i]))
            #self.trie[now].common+=1
            i+=1
        self.trie[now].end=id
        return ary
    
    def search(self,s):
        i=0
        now=0
        ary=[0]
        while i<len(s) and s[i] in self.trie[now].next_c_id:
            now=self.trie[now].next_c_id[s[i]]
            ary.append(now)
            i+=1
        if i<len(s):return []
        return ary
def main(s):
    tr=Trie()
    s.sort(key=lambda x:len(x))
    ans=0
    for i,x in enumerate(s):
        ary=tr.add(i,x)
        seen=set(())
        while ary:
            id=ary.pop()
            for nv in seen&tr.trie[id].next_c_id.keys():
                if tr.trie[tr.trie[id].next_c_id[nv]].end>=0 and tr.trie[tr.trie[id].next_c_id[nv]].end!=i:
                    ans+=1
            seen.add(tr.trie[id].c)
    print(ans)

if __name__=='__main__':
    a2n=lambda x:ord(x)-ord('a')
    n=int(input())
    s=[list(map(a2n,list(input()))) for _ in range(n)]
    [x.reverse() for x in s]
    main(s)

Submission status: Accepted

Solution code:
import sys
import string
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
T = [input()[::-1].strip() for i in range(N)]

#N = 100
#M = 10000
#import random
#import string
#T = [''.join(random.choices(string.ascii_lowercase, k=random.randint(M,M))) for i in range(N)]

class TrieTree:
    class Node:
        def __init__(self):
            #self.clue = defaultdict(int)
            self.clue = [0]*26
            self.ch = defaultdict(TrieTree.Node)
            self.cnt = 0
            self.end = False

    def __init__(self):
        self.root = self.Node()

    def register(self,word):
        node = self.root
        for w in word:
            node.cnt += 1
            node = node.ch[w]
        node.cnt += 1
        node.end = True
    
    def prefix(self, word):
        node = self.root
        for w in word:
            if w not in node.ch:
                return False
            else:
                node = node.ch[w]
        return node

tt = TrieTree()
for word in T:
    tt.register(word)

route = []

st = [tt.root]
while st:
    node = st.pop()
    route.append(node)
    st.extend(node.ch.values())

f = lambda c : ord(c)-97
for node in route[::-1]:
    for c,nnode in node.ch.items():
        for i,v in enumerate(nnode.clue):
            node.clue[i] += v
        node.clue[f(c)] += nnode.cnt - nnode.clue[f(c)]

ans = 0
for word in T:
    pre = word[:-1]
    last = word[-1]
    node = tt.prefix(pre)
    if not node:
        continue
    ans += node.clue[f(last)] - 1
    
print(ans)

Submission status: Accepted

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

import bisect
from collections import defaultdict

AZ = "abcdefghijklmnopqrstuvwxyz"
def DD(arg): return defaultdict(arg)

N = int(input())
words = [w[::-1] for w in list(input().strip() for _ in range(N))]
words.sort()
Lsortwords = sorted([(i,words[i]) for i in range(N)],key = lambda x:-len(x[1]))

class SegmentTree:
  def __init__(self, n, op, e):
    self.n = n
    self.op = op
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
    for i in range(self.size - 1, 0, -1):
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def update(self, i, val):
    i += self.size
    self.node[i] += val
    while i > 1:
      i >>= 1
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def get(self, l, r):
    l, r = l + self.size, r + self.size
    res_l, res_r = self.e, self.e
    while l < r:
      if l & 1:
        res_l = self.op(res_l, self.node[l])
        l += 1
      if r & 1:
        r -= 1
        res_r = self.op(self.node[r], res_r) 
      l, r = l >> 1, r >> 1
    return self.op(res_l, res_r)
  
ST = {l:SegmentTree(N,lambda a,b:a+b,0) for l in AZ}
check = [DD(int) for i in range(N)]
ans = 0
shori = 0
for i in range(len(Lsortwords[0][1]))[::-1]:
  for j,w in Lsortwords:
    if len(w) <= i: break
    if not check[j][w[i]]:
      ST[w[i]].update(j,1)
      check[j][w[i]] = 1
  while shori < N and len(Lsortwords[shori][1]) == i+1:
    w = Lsortwords[shori][1]
    p = w[:-1]
    q = w[-1]
    l = bisect.bisect_left(words,p)
    r = bisect.bisect(words,p+chr(97 + 26))
    ans += ST[q].get(l,r)-1
    shori += 1
    if shori == N: break
      
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#############
# Main Code #
#############

N = I()
words = [w[::-1] for w in SLs(N)]
words.sort()
Lsortwords = sorted([(i,words[i]) for i in range(N)],key = lambda x:-len(x[1]))

class SegmentTree:
  def __init__(self, n, op, e):
    self.n = n
    self.op = op
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
    for i in range(self.size - 1, 0, -1):
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def update(self, i, val):
    i += self.size
    self.node[i] += val
    while i > 1:
      i >>= 1
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def get(self, l, r):
    l, r = l + self.size, r + self.size
    res_l, res_r = self.e, self.e
    while l < r:
      if l & 1:
        res_l = self.op(res_l, self.node[l])
        l += 1
      if r & 1:
        r -= 1
        res_r = self.op(self.node[r], res_r) 
      l, r = l >> 1, r >> 1
    return self.op(res_l, res_r)
  
ST = {l:SegmentTree(N,lambda a,b:a+b,0) for l in AZ}
check = [DD(int) for i in range(N)]
ans = 0
shori = 0
for i in range(len(Lsortwords[0][1]))[::-1]:
  for j,w in Lsortwords:
    if len(w) <= i: break
    if not check[j][w[i]]:
      ST[w[i]].update(j,1)
      check[j][w[i]] = 1
  while shori < N and len(Lsortwords[shori][1]) == i+1:
    w = Lsortwords[shori][1]
    p = w[:-1]
    q = w[-1]
    l = bisect.bisect_left(words,p)
    r = bisect.bisect(words,p+chr(97 + 26))
    ans += ST[q].get(l,r)-1
    shori += 1
    if shori == N: break
      
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 61 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.defaultdict(int)
    ans = 0
    S = [SI() for _ in range(N)]
    for s in S:
        h = 0
        for i in range(len(s)-1,0,-1):
            h = (h * 27 + ord(s[i]) - ord('a') + 1) % MOD
        cnt[h] |= 1<<(ord(s[0])-ord('a'))

    for s in S:
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        h = 0
        for i in range(len(s)-1,0,-1):
            ans += bin(cnt[h] & a[i]).count('1')
            h = (h * 27 + ord(s[i]) - ord('a') + 1) % MOD

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#b（直し）
class TrieNode:
    def __init__(self):
        self.parent = None
        self.children = {}
    def new_child(self, key):
        self.children[key] = TrieNode()
        self.children[key].parent = self
        self.children[key].label = key
        return self.children[key]

import sys
def input(): return sys.stdin.readline().strip()

n = int(input())
s = [input() for _ in range(n)]
ans = -n # (Si, Si)
trie = TrieNode()
ends = set()

#build the trie
for si in s:
    cursor = trie
    for char in reversed(si):
        if char in cursor.children:
            cursor = cursor.children[char]
        else:
            cursor = cursor.new_child(char)
    else:
        ends.add(cursor)

#climb up the trie
for cursor in ends:
    head = set()
    while cursor.parent is not None:
        head.add(cursor.label)
        cursor = cursor.parent
        for char in cursor.children:
            if cursor.children[char] in ends and char in head:
                ans += 1
print(ans)

Submission status: Accepted

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

def solve():
    N = int(input())
    S = [input().rstrip()[::-1] for i in range(N)]
    S.sort(key=len)
    P = 2**61 - 1

    from collections import defaultdict
    D = defaultdict(lambda: [0]*26)

    ans = 0
    for s in S:
        l = ord(s[-1]) - ord('a')
        a = 0
        tmp = [0] * 26
        for c in s[:-1]:
            i = ord(c) - ord('a')
            if a in D:
                for j in range(26):
                    tmp[j] += D[a][j]
            ans += tmp[i]
            tmp[i] = 0
            a = (a*27 + i + 1) % P
        ans += tmp[l]
        D[a][l] += 1

    print(ans)
solve()

Submission status: Accepted

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

N = int(input())
S = [input().rstrip()[::-1] for i in range(N)]
S.sort(key=len)
P = 2**61 - 1

from collections import defaultdict
D = defaultdict(lambda: [0]*26)

ans = 0
for s in S:
    l = ord(s[-1]) - ord('a')
    a = 0
    tmp = [0] * 26
    for c in s[:-1]:
        i = ord(c) - ord('a')
        if a in D:
            for j in range(26):
                tmp[j] += D[a][j]
        ans += tmp[i]
        tmp[i] = 0
        a = (a*27 + i + 1) % P
    ans += tmp[l]
    D[a][l] += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

root = 10000
MOD = 2 ** 61 - 1


#"""
N = int(input())
S_list = [input() for _ in range(N)]
"""
def to_alpha(n):
    ret = ''
    while n > 0:
        n -= 1
        ret += chr(n % 26 + ord('a'))
        n //= 26
    return ret

N = 2 * 10 ** 5
S_list = [to_alpha(i) for i in range(2, 2 * N + 2, 2)]
#"""


S_list.sort(key=len)

ans = 0
wanted = defaultdict(set)
for S in S_list:
    suffix_hashes = [0]
    for c in S[-1:0:-1]:
        suffix_hashes.append((suffix_hashes[-1] * root + ord(c)) % MOD)
    suffix_hashes.reverse()
    l = len(S)
    alpha_set = set()
    for i, c in enumerate(S):
        alpha_set.add(c)
        # print(alpha_set, suffix_hashes[i])
        if suffix_hashes[i] in wanted:
            for alpha in wanted[suffix_hashes[i]]:
                if alpha in alpha_set:
                    ans += 1
    wanted[suffix_hashes[0]].add(S[0])
        
# print(wanted)
print(ans)

Submission status: Accepted

Solution code:
class RollingHash:
    def __init__(self,S,base,M):
        self.N=len(S)
        self.M=M
        self.H=[0]*(self.N+1)
        self.B=[0]*(self.N+1)
        self.B[0]=1
        for i in range(self.N):
            self.B[i+1]=self.B[i]*base%M
            self.H[i+1]=(self.H[i]*base+(ord(S[i])-96))%M
    def get(self,l,r):
        return (self.H[r]-self.H[l]*self.B[r-l]+self.M)%self.M

def main():
    import random

    N=int(input())
    M=2**61-1
    base=random.randrange(100,M)
    RH,S=[],[]
    RH,S=[None for i in range(N)],[None]*N
    for i in range(N):
        s=input()
        S[i]=s
        RH[i]=RollingHash(s,base,M)

    dic={}
    dic[0]=[0]*26
    for k,s in enumerate(S):
        Set=set()
        l=len(s)
        for j in range(l):
            Hash=RH[k].get(j,l)
            if not Hash in dic:
                dic[Hash]=[0]*26
            for c in Set:
                dic[Hash][ord(c)-97]+=1
            Set.add(s[j])
        for c in Set:
            dic[0][ord(c)-97]+=1
    ans=0
    for i,s in enumerate(S):
        Hash=RH[i].get(1,len(s))
        ans+=dic[Hash][ord(s[0])-97]-1
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

N=int(input())
S=[input().strip() for i in range(N)]
S.sort(key=len)

VLIST=[[set() for j in range(len(S[i]))] for i in range(N)]

for i in range(N):
    for j in range(len(S[i])):
        VLIST[i][j]=VLIST[i][j-1]|{S[i][j]}

# Trie木

Next_node_id=[[-1]*26] # "a"～"z"それぞれについて、対応する次のノードのid
Parent_id=[-1] # 親ノード
End=[[]] # そのノードを終端とするStringがあるか。ある場合、最後の一文字を入れる。

ANS=0

Nodes_id=1
for i in range(N):
    S2=S[i]
    L=len(S2)

    NOW=0
    for j in range(L-1,-1,-1):
        for s in End[NOW]:
            if s in VLIST[i][j]:
                ANS+=1

        if j==0:
            End[NOW].append(S2[0])
            continue
        
        NEXT=ord(S2[j])-97
        
        if Next_node_id[NOW][NEXT]==-1: # Nodeを追加する場合
            Next_node_id[NOW][NEXT]=Nodes_id

            Next_node_id.append([-1]*26)
            Parent_id.append(NOW)
            End.append([])

            NOW=Nodes_id         
            Nodes_id+=1

        else: # 追加しない場合
            NOW=Next_node_id[NOW][NEXT]

print(ANS)

Submission status: Accepted

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

N=int(input())
S=[input().strip() for i in range(N)]
S.sort(key=len)

VLIST=[[set() for j in range(len(S[i]))] for i in range(N)]

for i in range(N):
    for j in range(len(S[i])):
        VLIST[i][j]=VLIST[i][j-1]|{S[i][j]}

# ing木

Next_node_id=[[-1]*26] # "a"～"z"それぞれについて、対応する次のノードのid
Parent_id=[-1] # 親ノード
End=[[]] # そのノードを終端とするStringがあるか

ANS=0

Nodes_id=1
for i in range(N):
    S2=S[i]
    L=len(S2)

    NOW=0
    for j in range(L-1,-1,-1):
        for s in End[NOW]:
            if s in VLIST[i][j]:
                ANS+=1

        if j==0:
            End[NOW].append(S2[0])
            continue
        
        NEXT=ord(S2[j])-97
        
        if Next_node_id[NOW][NEXT]==-1: # Nodeを追加する場合
            Next_node_id[NOW][NEXT]=Nodes_id

            Next_node_id.append([-1]*26)
            Parent_id.append(NOW)
            End.append([])

            NOW=Nodes_id         
            Nodes_id+=1

        else: # 追加しない場合
            NOW=Next_node_id[NOW][NEXT]

print(ANS)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
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,v in c.items():
        if v>0:
          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)
  return 

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

Solution code:

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

class TrieNode:
    def __init__(self, n_alphabets):
        self.children = [None]*n_alphabets
        self.end = False

class Trie:
    def __init__(self, n_alphabets):
        self.n_alphabets = n_alphabets
        self.root = TrieNode(n_alphabets)

    def add(self, s):
        n = self.root
        for c in s:
            if n.children[c] is None:
                n.children[c] = TrieNode(self.n_alphabets)
            n = n.children[c]
        n.end = True


def solve(L):
    L = [tuple(ord(c)-ord('a') for c in reversed(s)) for s in L]
    trie = Trie(26)

    for s in L:
        trie.add(s)
    
    cnt = 0
    for s in L:

        app = [0]*26
        for c in s:
            app[c] += 1

        node = trie.root
        for c in s:
            if node is None:
                break
            for d,n in enumerate(node.children):
                if n is not None and app[d] > 0 and n.end:
                    cnt += 1
            app[c] -= 1
            node = node.children[c]
    return cnt - len(L)




if __name__ == '__main__':
    N = int(readline())
    L = [s.decode().rstrip() for s in read().split()]
    print(solve(L))

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from string import ascii_lowercase

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 19 + 7
EPS = 10 ** -10

class RollingHash:

    """ 文字列stringの部分文字列のハッシュを構築する。O(N) """
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MASK30 = (1 << 30) - 1
        self.MASK31 = (1 << 31) - 1
        self.MASK61 = (1 << 61) - 1
        self.MOD = self.MASK61
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)
 
        for i, char in enumerate(string):
            self.hash[i + 1] = self.calc_mod(self.mul(self.hash[i], self.BASE) + ord(char))
            self.pow[i + 1] = self.calc_mod(self.mul(self.pow[i], self.BASE))
 
    def calc_mod(self, x):
        """ x mod 2^61-1 を返す """
        xu = x >> 61
        xd = x & self.MASK61
        x = xu + xd
        if x >= self.MOD:
            x -= self.MASK61
        return x
 
    def mul(self, a, b):
        """ a*b mod 2^61-1 を返す """
        au = a >> 31
        ad = a & self.MASK31
        bu = b >> 31
        bd = b & self.MASK31
        mid = ad * bu + au * bd
        midu = mid >> 30
        midd = mid & self.MASK30
        return self.calc_mod(au * bu * 2 + midu + (midd << 31) + ad * bd)
 
    def get_hash(self, l, r):
        """ string[l,r)のハッシュ値を返すO(1) """
        res = self.calc_mod(self.hash[r] - self.mul(self.hash[l], self.pow[r - l]))
        return res
 
    def merge(self, h1, h2, length2):
        """ ハッシュ値h1と長さlength2のハッシュ値h2を結合するO(1) """
        return self.calc_mod(self.mul(h1, self.pow[length2]) + h2)
 
    def get_lcp(self, l1, r1, l2, r2):
        """
            string[l1:r2]とstring[l2:r2]の長共通接頭辞(Longest Common Prefix)の
            長さを求めるO(log|string|)
        """
        ng = min(r1 - l1, r2 - l2) + 1
        ok = 0
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if self.get_hash(l1, l1 + mid) == self.get_hash(l2, l2 + mid):
                ok = mid
            else:
                ng = mid
        return ok

N = INT()
se = set()
A = []
for i in range(N):
    s = input()
    s = s[::-1]
    rh = RollingHash(s)
    A.append((s, rh))
    se.add(rh.get_hash(0, len(s)))

ch = {}
for c in ascii_lowercase:
    ch[c] = RollingHash(c).get_hash(0, 1)

ans = 0
for s, rh in A:
    C = Counter(s)
    for i in range(len(s)):
        for c in C:
            if rh.merge(rh.get_hash(0, i), ch[c], 1) in se:
                ans += 1
        C[s[i]] -= 1
        if C[s[i]] == 0:
            del C[s[i]]
ans -= N
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from string import ascii_lowercase

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 19 + 7
EPS = 10 ** -10

class RollingHash:

    """ 文字列stringの部分文字列のハッシュを構築する。O(N) """
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MASK30 = (1 << 30) - 1
        self.MASK31 = (1 << 31) - 1
        self.MASK61 = (1 << 61) - 1
        self.MOD = self.MASK61
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)
 
        for i, char in enumerate(string):
            self.hash[i + 1] = self.calc_mod(self.mul(self.hash[i], self.BASE)
                                             + ord(char))
            self.pow[i + 1] = self.calc_mod(self.mul(self.pow[i], self.BASE))
 
    def calc_mod(self, x):
        """ x mod 2^61-1 を返す """
        xu = x >> 61
        xd = x & self.MASK61
        x = xu + xd
        if x >= self.MOD:
            x -= self.MASK61
        return x
 
    def mul(self, a, b):
        """ a*b mod 2^61-1 を返す """
        au = a >> 31
        ad = a & self.MASK31
        bu = b >> 31
        bd = b & self.MASK31
        mid = ad * bu + au * bd
        midu = mid >> 30
        midd = mid & self.MASK30
        return self.calc_mod(au * bu * 2 + midu + (midd << 31) + ad * bd)
 
    def get_hash(self, l, r):
        """ string[l,r)のハッシュ値を返すO(1) """
        res = self.calc_mod(self.hash[r]
                - self.mul(self.hash[l], self.pow[r - l]))
        return res
 
    def merge(self, h1, h2, length2):
        """ ハッシュ値h1と長さlength2のハッシュ値h2を結合するO(1) """
        return self.calc_mod(self.mul(h1, self.pow[length2]) + h2)
 
    def get_lcp(self, l1, r1, l2, r2):
        """
            string[l1:r2]とstring[l2:r2]の長共通接頭辞(Longest Common Prefix)の
            長さを求めるO(log|string|)
        """
        ng = min(r1 - l1, r2 - l2) + 1
        ok = 0
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if self.get_hash(l1, l1 + mid) == self.get_hash(l2, l2 + mid):
                ok = mid
            else:
                ng = mid
        return ok

N = INT()
se = set()
A = []
for i in range(N):
    s = input()
    s = s[::-1]
    rh = RollingHash(s)
    A.append((s, rh))
    se.add(rh.get_hash(0, len(s)))

ch = [0] * 26
for i, c in enumerate(ascii_lowercase):
    ch[i] = RollingHash(c).get_hash(0, 1)

ans = 0
for s, rh in A:
    C = Counter(s)
    for i in range(len(s)):
        for j, c in enumerate(ascii_lowercase):
            if C[c]:
                if rh.merge(rh.get_hash(0, i), ch[j], 1) in se:
                    ans += 1
        C[s[i]] -= 1
        if C[s[i]] == 0:
            del C[s[i]]
ans -= N
print(ans)

Submission status: Accepted

Solution code:
class Trie():
	def __init__(self,arrRev):
		self.node = [ [] for _ in range(len(arrRev)) ]
		# self.children = [ [ -1 for _ in range(ord('z')-ord('a'))] for _ in range(10**6+1) ]
		self.children = [ {} for _ in range(10**6+1) ]
		self.isHeadCharNode = [ False for _ in range( 10**6+1 ) ]
		nodeNumbering = 1
		for i,s in enumerate(arrRev):
			currentNode = 0
			for j,c in enumerate(list(s)):
				self.node[i].append( currentNode )
				if c not in self.children[currentNode]:
					self.children[currentNode][c] = nodeNumbering
					# print( currentNode, c, self.children[currentNode][c] )
					nodeNumbering += 1
				currentNode = self.children[currentNode][c]

			self.isHeadCharNode[currentNode] = True
			# print(currentNode, True)

	def getAnsCount(self,arrRev):

		ret = 0
		for i,s in enumerate(arrRev):
			prefixListOfLonger = set()
			for j in range( len(s)-1, -1, -1 ):
				# loop from leaf to root
				c = s[j]
				prefixListOfLonger.add(c)
				currentNode = self.node[i][j]

				for prefix in prefixListOfLonger:
					if prefix in self.children[currentNode] and self.isHeadCharNode[self.children[currentNode][prefix]]:
						# print(self.isHeadCharNode[self.children[currentNode][prefix]])
						ret += 1

		return ret



if __name__ == "__main__":
	ans=""
	N = int(input())
	lstW=[]

	for n in range(N):
		lstW.append(input()[::-1])

	# create Trie
	trie=Trie(lstW)
	ans = trie.getAnsCount(lstW) - N

	print( ans )

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
m = 2 ** 150 - 1
N = int(input())
X = sorted([input()[::-1] for _ in range(N)], key = len)

D = {}
ans = 0
for x in X:
    L = [0] * 26
    T, a = x[:-1], ord(x[-1]) - 97
    h = 0
    for t in T:
        if h in D:
            for i in range(26):
                L[i] += D[h][i]
        b = ord(t) - 97
        ans += L[b]
        L[b] = 0
        
        h = (h + b + 135 + (h << 11)) & m
    ans += L[a]
    if h in D:
        D[h][a] += 1
    else:
        D[h] = [0] * 26
        D[h][a] = 1
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
m = 2 ** 150 - 1
N = int(input())
X = sorted([input()[::-1] for _ in range(N)], key = len)

D = {}
ans = 0
for x in X:
    L = [0] * 26
    T, a = x[:-1], ord(x[-1]) - 97
    h = 0
    for t in T:
        if h in D:
            for i in range(26):
                L[i] += D[h][i]
        b = ord(t) - 97
        ans += L[b]
        L[b] = 0
        
        h = (h * 71 + b + 135) & m
    ans += L[a]
    if h in D:
        D[h][a] += 1
    else:
        D[h] = [0] * 26
        D[h][a] = 1
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
P = 10 ** 40 + 121
N = int(input())
X = sorted([input()[::-1] for _ in range(N)], key = len)

D = {}
ans = 0
for x in X:
    L = [0] * 26
    T, a = x[:-1], ord(x[-1]) - 97
    h = 0
    for t in T:
        if h in D:
            for i in range(26):
                L[i] += D[h][i]
        b = ord(t) - 97
        ans += L[b]
        L[b] = 0
        
        h = (h + b + 135) * 71 % P
    ans += L[a]
    if h in D:
        D[h][a] += 1
    else:
        D[h] = [0] * 26
        D[h][a] = 1
    
print(ans)

Submission status: Accepted

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


class RollingHash:
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MASK30 = (1 << 30) - 1
        self.MASK31 = (1 << 31) - 1
        self.MASK61 = (1 << 61) - 1
        self.MOD = self.MASK61
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)

        for i, char in enumerate(string):
            self.hash[i + 1] = self.calc_mod(self.mul(self.hash[i], self.BASE) + ord(char))
            self.pow[i + 1] = self.calc_mod(self.mul(self.pow[i], self.BASE))

    def calc_mod(self, x):
        """x mod 2^61-1 を返す。"""
        xu = x >> 61
        xd = x & self.MASK61
        x = xu + xd
        if x >= self.MOD:
            x -= MASK61
        return x

    def mul(self, a, b):
        """a*b mod 2^61-1 を返す。"""
        au = a >> 31
        ad = a & self.MASK31
        bu = b >> 31
        bd = b & self.MASK31
        mid = ad * bu + au * bd
        midu = mid >> 30
        midd = mid & self.MASK30
        return self.calc_mod(au * bu * 2 + midu + (midd << 31) + ad * bd)

    def get_hash(self, l, r):
        """string[l:r]のハッシュ値を返す。O(1)"""
        res = self.calc_mod(self.hash[r] - self.mul(self.hash[l], self.pow[r - l]))
        return res


n = int(input())
s = [input()[:-1] for i in range(n)]


s.sort(key=len)
str_set = set()
cnt = 0

for string in s:
    string = string[::-1]
    n = len(string)
    rh = RollingHash(string)

    for r in range(1, n + 1):
        if rh.get_hash(0, r) in str_set:
            cnt += 1

    set_char = set()
    for r in range(1, n + 1)[::-1]:
        set_char.add(string[r - 1])
        for char in set_char:
            if char == string[r - 1]:
                continue
            h = rh.calc_mod(rh.mul(rh.hash[r - 1], rh.BASE) + ord(char))
            if h in str_set:
                cnt += 1
    str_set.add(rh.get_hash(0, n))

print(cnt)