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,queue,math,copy,itertools,bisect,collections,heapq

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

    N = NI()
    cnt = collections.Counter()
    ans = 0
    C = []
    for _ in range(N):
        s = SI()
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        for i in range(len(s),-1,-1):
            if i == len(s):
                c = 0
            else:
                c = (c * 27 + ord(s[i]) - ord('a') + 1) % MOD
            if i > 0:
                d = c * 27
                for j in range(26):
                    if a[i-1] & (1<<j):
                        cnt[(d+j+1)%MOD] += 1
        C.append(c)
    for c in C:
        ans += cnt[c] - 1

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

Submission status: Wrong Answer

Solution code:
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections
N = int(sys.stdin.readline())
a = tuple(sys.stdin.readline().rstrip()[::-1] for _ in range(N)) # multi line with single param

root = {"children":{},"count":0}

for s in a:
    n = root
    n["count"] += 1
    for c in s:
        if not c in n["children"]:
            n["children"][c] = {"children":{},"count":0}
        n = n["children"][c]
        n["count"] += 1
    n["stop"] = s

#print(root)

def count(s):
    k = len(s)
    n = root
    i = 0
    for c in s[:-1]:
        #print(c,n)
        if not c in n["children"]:
            return 0
        n = n["children"][c]
    return n["count"]

print(sum(1 for b in [count(s) for s in a] if b>1))
#print(sum(count(s) for s in a))

Submission status: Wrong Answer

Solution code:
#QN = map(int,input().split()) # 500
N = int(input())

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

no = 1
cnt =0
for i in range(N):
  for j in range(N-no):
    


    s1_1 =list[i][0] 
    if (len(list[i]) == 1):
      isS1_2nd = False
    else:
      isS1_2nd = True
      s1_2 =list[i][1] 
    
    s2_1 =list[no+j][0] 
    if (len(list[no+j]) == 1):
      isS2_2nd = False
    else:
      isS2_2nd = True
      s2_2 =list[no+j][1]
    
    if (s1_1 == s2_1):
      cnt += 1
    elif(isS2_2nd  and (s1_1 == s2_2)):
      cnt +=1
    elif(isS1_2nd  and (s1_2 == s2_1)):
      cnt +=1
    elif(isS1_2nd  and isS2_2nd  and (s1_2 == s2_2)):
      cnt +=1
  no += 1

print("{}".format(cnt))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
S = [input()[::-1] for _ in range(N)]
d = defaultdict(lambda:defaultdict(lambda:0))
d0 = defaultdict(lambda:0)
for i in range(N):
    s = S[i]
    if len(s)>1:
        d[s[:-1]][s[-1]] += 1
    else:
        d0[s] += 1

ans = 0
for i in range(N):
    dt = {}
    for j in range(len(S[i])-2,-1,-1):
        dt[S[i][j+1]] = 0
        s = S[i][:j]

        if s in d:
            for ss in d[s]:
                if ss in dt:
                    ans += d[s][ss]

for i in range(N):
    if len(S[i])==1:
        ans += d0[S[i]]-1
    else:
        for s in d0:
            if s in S[i]:
                ans += d0[s]

print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
  n=int(input())
  l=[]
  S={}
  for i in range(n):
    s=input()
    l.append((len(s),s))
    S[s]=0
  for i,s in l:
    if i==1:
      continue
    for j in range(i):
      if s[j] in S:
        S[s]+=1
    for j in range(i-1):
      for k in range(j+1,i):
        x=s[j]+s[k:]
        if x==s:
          continue
        if x in S:
          S[x]+=1
  print(sum(S.values()))
    
if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 10 ** 9 + 7
mod = 1 << 35 - 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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 377777777
mod = 1 << 35 - 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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 37777774
mod = 1 << 61 - 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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 377777776
mod = 1 << 35 - 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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 37777
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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 3777
mod = 1 << 35 - 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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 1334
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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 1334
mod = 1 << 35 - 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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 1333
mod = 1 << 35 - 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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 221
mod = 1 << 35 - 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: Wrong Answer

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) - ord("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 + S[i]) % mod
  h = 0
  for i in range(l):
    h = (h * base + S[i]) % mod
    t |= 1 << S[i]
    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] * mod)
print(res)

Submission status: Wrong Answer

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

a = [list(map(lambda x: ord(x) - ord("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 + S[i]) % mod
  h = 0
  for i in range(l):
    h = (h * base + S[i]) % mod
    t |= 1 << S[i]
    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] * mod)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 37
md = 35
mod = 1 << md - 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 << md in s
  h = ord(S[0]) % mod
  rc = (v1 - h * pw[l - 1]) % mod
  s.add(rc + (ord(S[0]) - ord("a")) << md)
print(res)

Submission status: Wrong Answer

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

def load():
    num = int(input())
    strings = [input() for _ in range(num)]

    return strings


def get_pair(array):
    num = len(array)

    for i in range(num - 1):
        for j in range(i + 1, num):
            yield (array[i], array[j])

def limak_comparator(s1, s2):
    # spcieal case 1
    if len(s1) == len(s2):
        if s1 == s2:
            return True
        return False

    # special case 2
    if s1[0:2] == s2[0:2]:
        return False

    # normal case
    if len(s1) > len(s2):
        longer = s1
        shorter = s2
    else:
        longer = s2
        shorter = s1

    length = len(shorter)
    pointer = 0
    for c in longer:
        if c == shorter[pointer]:
            pointer += 1
            if pointer >= length:
                return True
    return False

if __name__ == "__main__":
    strings = load()
    counter = 0

    for s1, s2 in get_pair(strings):
        if limak_comparator(s1, s2):
            counter += 1

    print(counter)

Submission status: Wrong Answer

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]) >= len(x) 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]) >= len(x) 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: Wrong Answer

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

a = [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 in s
  rc = (h[l] - h[1] * pw[l - 1]) % mod
  s.add(rc + (ord(S[0]) - ord("a")))
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 37
mod = 1 << 37 - 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: Wrong Answer

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

a = [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: Wrong Answer

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

a = [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: Wrong Answer

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

a = [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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 221
mod = 1 << 36 - 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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 222
mod = 1 << 35 - 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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 37
mod = 1 << 31 - 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: Wrong Answer

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
N = int(input())
c = Counter()
base = 37
mod = 10 ** 9 + 7
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: 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

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 get_node(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]


    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 node_index,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):
            node=trie.get_node(cur)
            if node!=None:
                for a,val in se.items():
                    ai=alp2num(a)
                    cn=node.children[ai]
                    if cn!=-1 and trie.nodes[cn].item!=None:
                        ans+=trie.nodes[cn].item
                    
            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: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from random import randint
mod=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+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)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from random import randint
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*26+b)%(1<<200)
  ans+=y[a]
  if h not in d:d[h]=[0]*26
  d[h][a]+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from random import randint
mod=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])-ord("a")
  r=1
  h=0
  y=[0]*26
  for t in s[:-1]:
    b=ord(t)-ord("a")
    if h in d:
      for i in range(26):y[i]+=d[h][i]
    ans+=y[b]
    y[b]=0
    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)

Submission status: Wrong Answer

Solution code:
from random import randint
mod=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:
  x=ord(s[-1])-ord("a")
  r=1
  h=0
  y=[0]*27
  for t in s:y[ord(t)-ord("a")]+=1
  for t in s[:-1]:
    y[ord(t)-ord("a")]-=1
    h=(h+(ord(t)-ord("a"))*r)%mod
    r=(r*rr)%mod
    if h in d:
      for i in range(27):
        if y[i]:ans+=d[h][i]
  if h not in d:d[h]=[0]*27
  d[h][x]+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
P = 10 ** 18 + 3
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 + 5) * 7 % P
    ans += L[a]
    if h in D:
        D[h][a] += 1
    else:
        D[h] = [0] * 26
        D[h][a] = 1
    
print(ans)