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: Time Limit Exceeded

Solution code:
from collections import defaultdict

# Trie木をハッシュマップ（辞書）で再現
# Keyはその先祖のローリングハッシュ
# Valueはそれ自身とその子孫において、各アルファベットがいくつのSに現れるかの個数をリストでもったもの。

base = 2 ** 61 - 1
root = 10000
class RollingHash:

    def __init__(self, s):
        self.hs = [0] * (len(s) + 1)
        for i in range(len(s)):
            self.hs[i + 1] = self.hs[i] * root + ord(s[i]) % base

    def get_hash(self, l, r):
        "get the hash of s[l:r] (0 <= l <= r <= len(s))"
        return (self.hs[r] - self.hs[l] * pow(root, r - l, base)) % base

#"""
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 = 10 ** 5
S_list = [to_alpha(i) for i in range(2, 2 * N + 2, 2)]
#"""

S_list.sort(key = len, reverse = True)

trie_hash = defaultdict(lambda: [0] * 26)
ans = 0
for S in S_list:
    rh = RollingHash(S)

    ans += trie_hash[rh.get_hash(1, len(S))][ord(S[0]) - ord('a')]

    alphabet_counter = [0] * 26
    for i in range(len(S)):
        suffix_hash = rh.get_hash(i+1, len(S))
        alphabet_counter[ord(S[i]) - ord('a')] = 1
        for j in range(26):
            trie_hash[suffix_hash][j] += alphabet_counter[j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 221
mod = 1 << 37 - 1

a = [list(map(lambda x: ord(x), list(input())[: -1])) for _ in range(N)]
a.sort(key = len)
orda = ord("a")
pw = [1] * (len(a[-1]) + 1)
for i in range(len(a[-1])): pw[i + 1] = pw[i] * base % mod
res = 0
for S in a:
  l = len(S)
  t = 0
  v1 = 0
  h = [0] * (l + 1)
  for i in range(l):
    h[i + 1] = v1 = (v1 * base + S[i]) % mod
  for j in range(26):
    t = 0
    for i in range(l):
      t |= (S[i] - orda) == j
      if t:
        rc = (v1 - h[i + 1] * pw[l - (i + 1)]) % mod
        res += rc + j * mod in s
  rc = (v1 - h[1] * pw[l - 1]) % mod
  s.add(rc + (S[0] - orda) * mod)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 221
mod = 1 << 37 - 1

a = [list(map(lambda x: ord(x), list(input())[: -1])) for _ in range(N)]
a.sort(key = len)
orda = ord("a")
pw = [1] * (len(a[-1]) + 1)
for i in range(len(a[-1])): pw[i + 1] = pw[i] * base % mod
res = 0
for S in a:
  l = len(S)
  t = 0
  v1 = 0
  for i in range(l): v1 = (v1 * base + S[i]) % mod
  h = 0
  for i in range(l):
    h = (h * base + S[i]) % mod
    t |= 1 << (S[i] - orda)
    for j in range(26):
      if t & (1 << j):
        rc = (v1 - h * pw[l - (i + 1)]) % mod
        res += rc + j * mod in s
  h = S[0] % mod
  rc = (v1 - h * pw[l - 1]) % mod
  s.add(rc + (S[0] - orda) * mod)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 221
mod = 1 << 37 - 1

a = [list(input())[: -1] for _ in range(N)]
a.sort(key = len)
pw = [1] * (len(a[-1]) + 1)
for i in range(len(a[-1])): pw[i + 1] = pw[i] * base % mod
res = 0
for S in a:
  l = len(S)
  t = 0
  v1 = 0
  for i in range(l):
    v1 = (v1 * base + ord(S[i])) % mod
  h = 0
  for i in range(l):
    h = (h * base + ord(S[i])) % mod
    t |= 1 << (ord(S[i]) - ord("a"))
    for j in range(26):
      if t & (1 << j):
        rc = (v1 - h * pw[l - (i + 1)]) % mod
        res += rc + j * mod in s
  h = ord(S[0]) % mod
  rc = (v1 - h * pw[l - 1]) % mod
  s.add(rc + (ord(S[0]) - ord("a")) * mod)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 221
mod = 1 << 37 - 1

a = [list(input())[: -1] for _ in range(N)]
a.sort(key = len)
res = 0
for S in a:
  l = len(S)
  t = 0
  v1 = 0
  for i in range(l): v1 = (v1 * base + ord(S[i])) % mod
  h = 0
  for i in range(l):
    h = (h * base + ord(S[i])) % mod
    pw = pow(base, l - (i + 1), mod)
    t |= 1 << (ord(S[i]) - ord("a"))
    for j in range(26):
      if t & (1 << j):
        rc = (v1 - h * pw) % mod
        res += rc + j * mod in s
  h = ord(S[0]) % mod
  rc = (v1 - h * pow(base, l - 1, mod)) % mod
  s.add(rc + (ord(S[0]) - ord("a")) * mod)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 221
mod = 1 << 37 - 1

a = [list(input())[: -1] for _ in range(N)]
a.sort(key = len)
res = 0
for S in a:
  l = len(S)
  t = 0
  pw = [1] * (l + 1)
  v1 = 0
  v2 = 1
  for i in range(l):
    v1 = (v1 * base + ord(S[i])) % mod
    pw[i + 1] = v2 = v2 * base % mod
  v = 0
  for i in range(l):
    v = (v * base + ord(S[i])) % mod
    t |= 1 << (ord(S[i]) - ord("a"))
    for j in range(26):
      if t & (1 << j):
        rc = (v1 - v * pw[l - (i + 1)]) % mod
        res += rc + j * mod in s
  v = ord(S[0]) % mod
  rc = (v1 - v * pw[l - 1]) % mod
  s.add(rc + (ord(S[0]) - ord("a")) * mod)
print(res)

Submission status: Time Limit Exceeded

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 getall(self,L):
        arr=[]
        for i in range(L,self.N+1):
            arr.append(self.get(i-L,i))
        return arr

def Hash(S,base,M):
    H=0
    for c in S:
        H=(H*base+ord(c)-96)%M
    return H
    
import random

N=int(input())
M=2**61-1
base=random.randrange(100,M)
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]={}
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]={}
        for c in Set:
            if not c in dic[Hash]:
                dic[Hash][c]=1
            else:
                dic[Hash][c]+=1
        Set.add(s[j])
    for c in Set:
        if not c in dic[0]:
            dic[0][c]=1
        else:
            dic[0][c]+=1
ans=0
for i,s in enumerate(S):
    Hash=RH[i].get(1,len(s))
    ans+=dic[Hash][s[0]]-1
print(ans)

Submission status: Time Limit Exceeded

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 getall(self,L):
        arr=[]
        for i in range(L,self.N+1):
            arr.append(self.get(i-L,i))
        return arr

def Hash(S,base,M):
    H=0
    for c in S:
        H=(H*base+ord(c)-96)%M
    return H
    
import random
import sys
read=sys.stdin.readline

N=int(input())
M=2**61-1
base=random.randrange(100,M)
RH,S=[],[]
for i in range(N):
    s=read().rstrip()
    S.append(s)
    RH.append(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)

Submission status: Time Limit Exceeded

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 getall(self,L):
        arr=[]
        for i in range(L,self.N+1):
            arr.append(self.get(i-L,i))
        return arr

def Hash(S,base,M):
    H=0
    for c in S:
        H=(H*base+ord(c)-96)%M
    return H
    
import random


N=int(input())
M=2**61-1
base=random.randrange(100,M)
RH,S=[],[]
for i in range(N):
    s=input()
    S.append(s)
    RH.append(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)

Submission status: Time Limit Exceeded

Solution code:
def C(x):
    s = 0
    t = N
    for i in range(len(x)-1):
        t = upper_bound(x, i, s, t)
        s = lower_bound(x, i, s, t)
    
    res = 0
    for i in range(s, t):
        if x[-1] in S[i][len(x)-1:]:
            res += 1
    
    return res - 1
    

def lower_bound(x, i, s, t):
    s, t = s-1, t
    while t - s > 1:
        m = (s + t) // 2
        if len(S[m]) > i and S[m][i] >= x[i]:
            t = m
        else:
            s = m
    
    return t

def upper_bound(x, i, s, t):
    s, t = s-1, t
    while t - s > 1:
        m = (s + t) // 2
        if len(S[m]) > i and S[m][i] > x[i]:
            t = m
        else:
            s = m
    
    return t
    

N = int(input())
S = [tuple(reversed(input())) for _ in range(N)]
S.sort()
ans = 0
for x in S:
    ans += C(x)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 37
mod = 1 << 45 - 1

a = [input()[: -1] for _ in range(N)]
a.sort(key = len)
res = 0
for S in a:
  l = len(S)
  pw = [1] * (l + 1)
  h = [0] * (l + 1)
  v1 = 0
  v2 = 1
  for i in range(l):
    h[i + 1] = v1 = (v1 * base + ord(S[i])) % mod
    pw[i + 1] = v2 = v2 * base % mod
  ss = set()
  for i in range(l):
    ss.add(ord(S[i]) - ord("a"))
    for j in ss:
      rc = (h[l] - h[i + 1] * pw[l - (i + 1)]) % mod
      res += rc + j * mod in s
  rc = (h[l] - h[1] * pw[l - 1]) % mod
  s.add(rc + (ord(S[0]) - ord("a")) * mod)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 221
mod = 1 << 37 - 1

a = [list(input())[: -1] for _ in range(N)]
a.sort(key = len)
res = 0
for S in a:
  l = len(S)
  t = 0
  pw = [1] * (l + 1)
  h = [0] * (l + 1)
  v1 = 0
  v2 = 1
  for i in range(l):
    h[i + 1] = v1 = (v1 * base + ord(S[i])) % mod
    pw[i + 1] = v2 = v2 * base % mod
  for i in range(l):
    t |= 1 << (ord(S[i]) - ord("a"))
    for j in range(26):
      if t & (1 << j):
        rc = (h[l] - h[i + 1] * pw[l - (i + 1)]) % mod
        res += rc + j * mod in s
  rc = (h[l] - h[1] * pw[l - 1]) % mod
  s.add(rc + (ord(S[0]) - ord("a")) * mod)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 221
mod = 1 << 37 - 1

a = [list(input())[: -1] for _ in range(N)]
a.sort(key = len)
res = 0
for S in a:
  l = len(S)
  table = [0] * l
  t = 0
  pw = [1] * (l + 1)
  h = [0] * (l + 1)
  v1 = 0
  v2 = 1
  for i in range(l):
    h[i + 1] = v1 = (v1 * base + ord(S[i])) % mod
    pw[i + 1] = v2 = v2 * base % mod
    t |= 1 << (ord(S[i]) - ord("a"))
    table[i] = t
  for i in range(l):
    for j in range(26):
      if table[i] & (1 << j):
        rc = (h[l] - h[i + 1] * pw[l - (i + 1)]) % mod
        res += rc + j * mod in s
  rc = (h[l] - h[1] * pw[l - 1]) % mod
  s.add(rc + (ord(S[0]) - ord("a")) * mod)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 37
mod = 1 << 40 - 1

a = [list(input())[: -1] for _ in range(N)]
a.sort(key = len)
res = 0
for S in a:
  l = len(S)
  table = [0] * l
  t = 0
  pw = [1] * (l + 1)
  h = [0] * (l + 1)
  v1 = 0
  v2 = 1
  for i in range(l):
    h[i + 1] = v1 = (v1 * base + ord(S[i])) % mod
    pw[i + 1] = v2 = v2 * base % mod
    t |= 1 << (ord(S[i]) - ord("a"))
    table[i] = t
  for i in range(l):
    for j in range(26):
      if table[i] & (1 << j):
        rc = (h[l] - h[i + 1] * pw[l - (i + 1)]) % mod
        res += rc + j * mod in s
  rc = (h[l] - h[1] * pw[l - 1]) % mod
  s.add(rc + (ord(S[0]) - ord("a")) * mod)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 37
mod = 1 << 45 - 1

a = [list(input())[: -1] for _ in range(N)]
a.sort(key = len)
res = 0
for S in a:
  l = len(S)
  table = [0] * l
  t = 0
  pw = [1] * (l + 1)
  h = [0] * (l + 1)
  v1 = 0
  v2 = 1
  for i in range(l):
    h[i + 1] = v1 = (v1 * base + ord(S[i])) % mod
    pw[i + 1] = v2 = v2 * base % mod
    t |= 1 << (ord(S[i]) - ord("a"))
    table[i] = t
  for i in range(l):
    for j in range(26):
      if table[i] & (1 << j):
        rc = (h[l] - h[i + 1] * pw[l - (i + 1)]) % mod
        res += rc + j * mod in s
  rc = (h[l] - h[1] * pw[l - 1]) % mod
  s.add(rc + (ord(S[0]) - ord("a")) * mod)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 37
mod = 1 << 61 - 1

a = [list(input())[: -1] for _ in range(N)]
a.sort(key = len)
res = 0
for S in a:
  l = len(S)
  table = [0] * l
  t = 0
  pw = [1] * (l + 1)
  h = [0] * (l + 1)
  v1 = 0
  v2 = 1
  for i in range(l):
    h[i + 1] = v1 = (v1 * base + ord(S[i])) % mod
    pw[i + 1] = v2 = v2 * base % mod
    t |= 1 << (ord(S[i]) - ord("a"))
    table[i] = t
  for i in range(l):
    for j in range(26):
      if table[i] & (1 << j):
        rc = (h[l] - h[i + 1] * pw[l - (i + 1)]) % mod
        res += rc + j * mod in s
  rc = (h[l] - h[1] * pw[l - 1]) % mod
  s.add(rc + (ord(S[0]) - ord("a")) * mod)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
N = int(input())
c = Counter()
base = 37
mod = 1 << 61 - 1

a = [list(input())[: -1] for _ in range(N)]
a.sort(key = len)
res = 0
for S in a:
  l = len(S)
  table = [0] * l
  t = 0
  pw = [1] * (l + 1)
  h = [0] * (l + 1)
  v1 = 0
  v2 = 1
  for i in range(l):
    h[i + 1] = v1 = (v1 * base + ord(S[i])) % mod
    pw[i + 1] = v2 = v2 * base % mod
    t |= 1 << (ord(S[i]) - ord("a"))
    table[i] = t
  for i in range(l):
    for j in range(26):
      if table[i] & (1 << j):
        rc = (h[l] - h[i + 1] * pw[l - (i + 1)]) % mod
        res += c[rc + j * mod]
  rc = (h[l] - h[1] * pw[l - 1]) % mod
  c[rc + (ord(S[0]) - ord("a")) * mod] += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
N = int(input())
c = Counter()
base = 37
mod = 1 << 61 - 1

a = []
for _ in range(N):
  S = list(input())[: -1]
  l = len(S)
  table = [0] * l
  t = 0
  pw = [1] * (l + 1)
  h = [0] * (l + 1)
  v1 = 0
  v2 = 1
  for i in range(l):
    h[i + 1] = v1 = (v1 * base + ord(S[i])) % mod
    pw[i + 1] = v2 = v2 * base % mod
    t |= 1 << (ord(S[i]) - ord("a"))
    table[i] = t
  for i in range(l):
    for j in range(26):
      if table[i] & (1 << j):
        rc = (h[l] - h[i + 1] * pw[l - (i + 1)]) % mod
        c[rc + j * mod] += 1
  rc = (h[l] - h[1] * pw[l - 1]) % mod
  a.append((rc + (ord(S[0]) - ord("a")) * mod))
res = 0
#print(a, c)
for t in a: res += c[t] - 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
N = int(input())
c = Counter()
base = 37
mod = 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):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
a = []
for _ in range(N):
  S = list(input())[: -1]
  rc = RollingHash(S, base, mod)
  table = [0] * len(S)
  t = 0
  for i in range(len(S)):
    t |= 1 << (ord(S[i]) - ord("a"))
    table[i] = t
  for i in range(len(S)):
    for j in range(26):
      if table[i] & (1 << j): c[(rc.get(i + 1, len(S)) + j * mod)] += 1
  a.append((rc.get(1, len(S)) + (ord(S[0]) - ord("a")) * mod))
res = 0
#print(a, c)
for t in a: res += c[t] - 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
N = int(input())
c = Counter()
base = 37
mod = 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):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
a = []
for _ in range(N):
  S = list(input())[: -1]
  rc = RollingHash(S, base, mod)
  table = [0] * len(S)
  t = 0
  for i in range(len(S)):
    t |= 1 << (ord(S[i]) - ord("a"))
    table[i] = t
  for i in range(len(S)):
    for j in range(26):
      if table[i] & (1 << j): c[(rc.get(i + 1, len(S)), j)] += 1
  a.append((rc.get(1, len(S)), ord(S[0]) - ord("a")))
res = 0
#print(a, c)
for t in a: res += c[t] - 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=[input() 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: Time Limit Exceeded

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

VOCAB_SIZE = 26 # 語彙数(小文字なら26)
class TrieNode:
    """  Trie木のノード
    item : 単語に登録するvalue, 単語終端ノード以外の場合はNone
    children : list 子ノードのリスト
    """

    def __init__(self, item = None):
        self.item = item
        self.children = [-1 for i in range(VOCAB_SIZE)]

    def __str__(self):
        ret = ""
        ret = ret + "item = {}\n".format(self.item)
        ret = ret + "children = \n{}".format(self.children)
        return ret

class Trie:
    def __init__(self):
        root = TrieNode()
        self.nodes = [root]

    def __add_node(self, node):
        self.nodes.append(node)
        return len(self.nodes) - 1

    def __get_char_num(self, c):
        #文字列の番号を返す関数
        return ord(c) - ord('a')

    def insert(self ,word, item):
        """Trieに新しい単語を登録する
        word : str 登録する単語
        item : wordに格納するvalue
        """
        char_index=0; node_index=0
        lw=len(word)
        for char_index in range(lw):
            char_num = self.__get_char_num(word[char_index])
            next_node_index = self.nodes[node_index].children[char_num]
            if next_node_index == -1:
                # 現在のノードにword[char_index]での遷移がなかった場合
                new_node = TrieNode()
                next_node_index = self.__add_node(new_node)
                self.nodes[node_index].children[char_num] = next_node_index
            node_index=next_node_index
            
        self.nodes[node_index].item = item

    def query(self, word):
        """
        検索
        word : str
        return : node.item or None
        """
        node_index = 0

        for c in word:
            char_num = self.__get_char_num(c)
            tmp_node = self.nodes[node_index]
            
            node_index = tmp_node.children[char_num]
            if node_index == -1:
                return None

        return self.nodes[node_index].item

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)
    trie=Trie()
    for im in inds:
        
        s=L[im]

        ls=len(s)
        cur=""
        se=Counter(s)
        #printe(se)
        for i in range(ls):
            for a,val in se.items():
                if val:
                    q=trie.query(cur+a)
                    if q!=None:
                        ans+=q
                    
            si=s[-1-i]
            cur=cur+si
            #cur2=(cur2*base+sin)%mod2

            se[si]-=1
        q=trie.query(cur)
        if q==None:
            q=0
        trie.insert(cur,q+1)

    print(ans)
            





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal

INF = 1 << 50



def run():
    N = int(input())
    lasts = defaultdict(lambda:[])
    lengths = set()
    S = []
    for i in range(N):
        s = input()
        S.append(s)
        lasts[s[1:]].append(i)
        lengths.add(len(s)-1)
    #print(lasts)
    #print(lengths)
    ans = 0
    for s in S:
        for l in lengths:
            if l == 0:
                if '' in lasts.keys():
                    for k in lasts['']:
                        if S[k][0] in s:
                            ans += 1
                            #print(s, l, S[k])
            else:
                if s[-l:] in lasts.keys():
                    for k in lasts[s[-l:]]:
                        if S[k][0] in s[:-l]:
                            ans += 1
                            #print(s, l, S[k])

    print(ans-N)



    

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

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

N = INT()
se = set()
for i in range(N):
    s = input()
    s = s[::-1]
    se.add(s)

ans = 0
for s in se:
    C = Counter(s)
    pre = []
    for i in range(len(s)):
        for c in ascii_lowercase:
            if C[c]:
                if ''.join(pre)+c in se:
                    ans += 1
        pre += [s[i]]
        C[s[i]] -= 1
        if C[s[i]] == 0:
            del C[s[i]]
ans -= N
print(ans)

Submission status: Time Limit Exceeded

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

N = INT()
se = set()
for i in range(N):
    s = input()
    s = s[::-1]
    se.add(s)

ans = 0
for s in se:
    C = Counter(s)
    pre = ''
    for i in range(len(s)):
        for c in ascii_lowercase:
            if C[c]:
                if pre+c in se:
                    ans += 1
        pre += s[i]
        C[s[i]] -= 1
        if C[s[i]] == 0:
            del C[s[i]]
ans -= N
print(ans)

Submission status: Time Limit Exceeded

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

N = INT()
se = set()
for i in range(N):
    s = input()
    s = s[::-1]
    se.add(s)

ans = 0
for s in se:
    C = Counter(s)
    for i in range(len(s)):
        for c in ascii_lowercase:
            if C[c]:
                if s[:i]+c in se:
                    ans += 1
        C[s[i]] -= 1
        if C[s[i]] == 0:
            del C[s[i]]
ans -= N
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
m=2**150-1
n=int(input())
ss=[input()[::-1]for _ in range(n)]
ss.sort(key=len)
d={}
ans=0
for s in ss:
  a=ord(s[-1])-97
  r=1
  h=0
  y=[0]*26
  for t in s[:-1]:
    b=ord(t)-97
    if h in d:
      for i in range(26):y[i]+=d[h][i]
    ans+=y[b]
    y[b]=0
    h=(h*71+b+135)&m
  ans+=y[a]
  if h not in d:d[h]=[0]*26
  d[h][a]+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from random import randint
mod=(1<<150)-1#1370757747362922367
rr=randint(2,mod-2)
n=int(input())
ss=[input()[::-1]for _ in range(n)]
ss.sort(key=len)
d={}
ans=0
for s in ss:
  a=ord(s[-1])-97
  r=1
  h=0
  y=[0]*26
  for t in s[:-1]:
    b=ord(t)-97
    if h in d:
      for i in range(26):y[i]+=d[h][i]
    ans+=y[b]
    y[b]=0
    h=(h*71+b+135)&mod
    #h=(h+b*r)%mod
    #r=r*rr%mod
  ans+=y[a]
  if h not in d:d[h]=[0]*26
  d[h][a]+=1
print(ans)