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
input = lambda: sys.stdin.readline().rstrip()
P = 10 ** 30 + 57
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) * 7 % 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: 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) * 7 % 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: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
P = 10 ** 9 + 7
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) * 7 % 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: Wrong Answer

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


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

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

    def get_hash(self, l, r):
        """string[l:r]のハッシュ値を返す。O(1)"""
        res = (self.hash[r] - self.hash[l] * self.pow[r - l]) % self.MOD
        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.hash[r - 1] + ord(char)) * rh.BASE % rh.MOD
            if h in str_set:
                cnt += 1
    str_set.add(rh.get_hash(0, n))

print(cnt)

Submission status: Wrong Answer

Solution code:
import collections
N, *S = [s + 'z' for s in open(0).read().split()]
S.sort(key=len)
N = int(N[:-1])
cnt = [collections.defaultdict(int) for _ in range(N)]
for i, s in enumerate(S):
    for c in s:
        cnt[i][c] += 1
rollinghash = [0] * N
mod = 2**61 - 1
j = -1
ans = 0
se = {'z': {range(N)}}
imin = 0
for j in range(-1, -len(S[-1]) - 1, -1):
    for i in range(imin, N):
        if j == -len(S[i]):
            ans += sum(cnt[p][S[i][0]] > 0 for p in se[rollinghash[i]]) - 1
    for i in range(imin, N):
        if j == -len(S[i]):
            imin += 1
        cnt[i][S[i][j]] -= 1
    se = collections.defaultdict(set)
    for i in range(imin, N):
        rollinghash[i] *= 32
        rollinghash[i] += ord(S[i][j]) - 97
        rollinghash[i] &= mod
        se[rollinghash[i]].add(i)
    j -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N, *S = [s + 'z' for s in open(0).read().split()]
S.sort(key=len)
N = int(N[:-1])
cnt = [collections.defaultdict(int) for _ in range(N)]
for i, s in enumerate(S):
    for c in s:
        cnt[i][c] += 1
rollinghash = [0] * N
mod = 2**61 - 1
k = 32
j = -1
ans = 0
se = {'z': {range(N)}}
imin = 0
for j in range(-1, -len(S[-1]) - 1, -1):
    for i in range(imin, N):
        if j == -len(S[i]):
            ans += sum(cnt[p][S[i][0]] > 0 for p in se[rollinghash[i]]) - 1
    for i in range(imin, N):
        if j == -len(S[i]):
            imin += 1
        cnt[i][S[i][j]] -= 1
    se = collections.defaultdict(set)
    for i in range(imin, N):
        rollinghash[i] *= k
        rollinghash[i] += ord(S[i][j]) - 97
        rollinghash[i] &= mod
        se[rollinghash[i]].add(i)
    j -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N, *S = [s + 'z' for s in open(0).read().split()]
S.sort(key=len)
N = int(N[:-1])
cnt = [collections.defaultdict(int) for _ in range(N)]
for i, s in enumerate(S):
    for c in s:
        cnt[i][c] += 1
rollinghash = [0] * N
mod = 2**31 - 1
k = 2**10
j = -1
ans = 0
se = {'z': {range(N)}}
imin = 0
for j in range(-1, -len(S[-1]) - 1, -1):
    for i in range(imin, N):
        if j == -len(S[i]):
            ans += sum(cnt[p][S[i][0]] > 0 for p in se[rollinghash[i]]) - 1
    for i in range(imin, N):
        if j == -len(S[i]):
            imin += 1
        cnt[i][S[i][j]] -= 1
    se = collections.defaultdict(set)
    for i in range(imin, N):
        rollinghash[i] *= k
        rollinghash[i] += ord(S[i][j])
        rollinghash[i] &= mod
        se[rollinghash[i]].add(i)
    j -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N, *S = [s + 'z' for s in open(0).read().split()]
N = int(N[:-1])
cnt = [collections.defaultdict(int) for _ in range(N)]
for i, s in enumerate(S):
    for c in s:
        cnt[i][c] += 1
cand = set(range(N))
rollinghash = [0] * N
mod = 10**9 + 7
j = -1
ans = 0
se = {'z': {range(N)}}
while cand:
    for i in cand:
        if j == -len(S[i]):
            ans += sum(cnt[p][S[i][0]] > 0 for p in se[rollinghash[i]]) - 1
    for i in cand.copy():
        if j == -len(S[i]):
            cand.remove(i)
        cnt[i][S[i][j]] -= 1
    se = collections.defaultdict(set)
    for i in cand:
        rollinghash[i] *= 26
        rollinghash[i] += ord(S[i][j]) - 97
        rollinghash[i] %= mod
        se[rollinghash[i]].add(i)
    j -= 1
print(ans)
'''e
1234
 134
 234
  14
  24
  34
   1
   2
   3
   4
'''

Submission status: Wrong Answer

Solution code:
import collections
N, *S = [s + 'z' for s in open(0).read().split()]
N = int(N[:-1])
cnt = [collections.defaultdict(int) for _ in range(N)]
for i, s in enumerate(S):
    for c in s:
        cnt[i][c] += 1
cand = set(range(N))
rollinghash = [0] * N
mod = 2**31 - 1
j = -1
ans = 0
se = {'z': {range(N)}}
while cand:
    for i in cand:
        if j == -len(S[i]):
            ans += sum(cnt[p][S[i][0]] > 0 for p in se[rollinghash[i]]) - 1
    for i in cand.copy():
        if j == -len(S[i]):
            cand.remove(i)
        cnt[i][S[i][j]] -= 1
    se = collections.defaultdict(set)
    for i in cand:
        rollinghash[i] *= 26
        rollinghash[i] += ord(S[i][j]) - 97
        rollinghash[i] %= mod
        se[rollinghash[i]].add(i)
    j -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
words = [list(input())[::-1] for _ in range(n)]
a = ord("a")
words.sort(key=lambda x: len(x))
paths = [[] for _ in range(n)]
child = [[0] * (26) for _ in range(10 ** 6 + 10)]
is_end = [False] * (10 ** 6 + 10)
nxt = 1
for i in range(n):
    word = words[i]
    nagasa = len(word)
    node = 0
    for j in range(nagasa):
        num = ord(word[j]) - a
        paths[i].append(node)
        if child[node][num] == 0:
            child[node][num] = nxt
            nxt += 1
        node = child[node][num]
    is_end[node] = True

ans = 0
for i in range(n):
    word = words[i]
    kouho = []
    nagasa = len(word)
    for j in range(nagasa - 1, -1, -1):
        kouho.append(word[j])
        node = paths[i][j]
        for s in kouho[::-1]:
            num = ord(s) - a
            ans += is_end[child[node][num]]
print(ans - n)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

root = 10000
MOD = 998244353
def rolling_hash(s):
    hs = [0] * (len(s) + 1)
    for i in range(len(s)):
        hs[i + 1] = hs[i] * root + ord(s[i]) % MOD
    return hs

#"""
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)

ans = 0
wanted = {chr(i): set() for i in range(ord('a'), ord('z') + 1)}
for S in S_list:
    alpha_set = set()
    hash_of_S = rolling_hash(S)
    for i in range(len(S)):
        alpha_set.add(S[i])
        suffix_hash = (hash_of_S[len(S)] - hash_of_S[i+1] * pow(root, (len(S) - i - 1), MOD)) % MOD
        for alpha in alpha_set:
            if suffix_hash in wanted[alpha]:
                ans += 1

    suffix_of_S = (hash_of_S[len(S)] - hash_of_S[1] * pow(root, (len(S) - 1), MOD)) % MOD
    wanted[S[0]].add(suffix_of_S)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

root = 10000
MOD = 2 ** 61 - 1
def rolling_hash(s):
    hs = [0] * (len(s) + 1)
    for i in range(len(s)):
        hs[i + 1] = hs[i] * root + ord(s[i]) % MOD
    return hs

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

ans = 0
wanted = {chr(i): set() for i in range(ord('a'), ord('z') + 1)}
for S in S_list:
    alpha_set = set()
    hash_of_S = rolling_hash(S)
    for i in range(len(S)):
        alpha_set.add(S[i])
        suffix_hash = (hash_of_S[len(S)] - hash_of_S[i+1] * pow(root, (len(S) - i - 1), MOD)) % MOD
        for alpha in alpha_set:
            if suffix_hash in wanted[alpha]:
                ans += 1

    suffix_of_S = (hash_of_S[len(S)] - hash_of_S[1] * pow(root, (len(S) - 1), MOD)) % MOD
    wanted[S[0]].add(suffix_of_S)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

root = 10000
MOD = 10 ** 9 + 7
def rolling_hash(s):
    hs = [0] * (len(s) + 1)
    for i in range(len(s)):
        hs[i + 1] = hs[i] * root + ord(s[i]) % MOD
    return hs

#"""
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'))
    return ret

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


S_list.sort(key=len)

ans = 0
wanted = {chr(i): set() for i in range(ord('a'), ord('z') + 1)}
for S in S_list:
    alpha_set = set()
    hash_of_S = rolling_hash(S)
    for i in range(len(S)):
        alpha_set.add(S[i])
        suffix_hash = (hash_of_S[len(S)] - hash_of_S[i+1] * pow(root, (len(S) - i - 1), MOD)) % MOD
        for alpha in alpha_set:
            if suffix_hash in wanted[alpha]:
                ans += 1

    suffix_of_S = (hash_of_S[len(S)] - hash_of_S[1] * pow(root, (len(S) - 1), MOD)) % MOD
    wanted[S[0]].add(suffix_of_S)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
words = [list(input())[::-1] for _ in range(n)]
a = ord("a")
words.sort(key=lambda x: len(x), reverse=True)
paths = [[] for _ in range(n)]
child = [[0] * (26) for _ in range(10 ** 6 + 10)]
is_end = [False] * (10 ** 6 + 10)
nxt = 1
for i in range(n):
    word = words[i]
    nagasa = len(word)
    node = 0
    for j in range(nagasa):
        num = ord(word[j]) - a
        paths[i].append(node)
        if child[node][num] == 0:
            child[node][num] = nxt
            nxt += 1
        node = child[node][num]
    is_end[node] = True

ans = 0
for i in range(n):
    word = words[i]
    kouho = []
    nagasa = len(word)
    for j in range(nagasa - 1, -1, -1):
        kouho.append(word[j])
        node = paths[i][j]
        for s in kouho[::-1]:
            num = ord(s) - a
            ans += is_end[child[node][num]]
print(ans - n)

Submission status: Wrong Answer

Solution code:
n = int(input())
words = [list(input()) for _ in range(n)]
a = ord("a")

paths = [[] for _ in range(n)]
child = [[0] * (26) for _ in range(10 ** 6 + 10)]
is_end = [False] * (10 ** 6 + 10)
nxt = 1
for i in range(n):
    word = list(words[i])[::-1]
    words[i] = word
    nagasa = len(word)
    node = 0
    for j in range(nagasa):
        num = ord(word[j]) - a
        paths[i].append(node)
        if child[node][num] == 0:
            child[node][num] = nxt
            nxt += 1
        node = child[node][num]
    is_end[node] = True

ans = 0
for i in range(n):
    word = words[i]
    kouho = []
    nagasa = len(word)
    for j in range(nagasa - 1, -1, -1):
        kouho.append(word[j])
        node = paths[i][j]
        for s in kouho[::-1]:
            num = ord(s) - a
            ans += is_end[child[node][num]]
print(ans - n)

Submission status: Wrong Answer

Solution code:
n = int(input())
words = [list(input()) for _ in range(n)]
a = ord("a")

paths = [[] for _ in range(n)]
child = [[0] * (26) for _ in range(10 ** 6 + 10)]
is_end = [False] * (10 ** 6 + 10)
nxt = 1
for i in range(n):
    word = list(words[i])[::-1]
    words[i] = word
    nagasa = len(word)
    node = 0
    for j in range(nagasa):
        num = ord(word[j]) - a
        paths[i].append(node)
        if child[node][num] == 0:
            child[node][num] = nxt
            nxt += 1
        node = child[node][num]
    is_end[node] += 1

ans = 0
for i in range(n):
    word = words[i]
    kouho = []
    nagasa = len(word)
    for j in range(nagasa - 1, -1, -1):
        kouho.append(word[j])
        node = paths[i][j]
        for s in kouho[::-1]:
            num = ord(s) - a
            ans += is_end[child[node][num]]
print(ans - n)

Submission status: Wrong Answer

Solution code:
'''
自宅用PCでの解答
https://atcoder.jp/contests/agc047/editorial/43を参考にpythonで実装
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"



def main():
    n = int(ipt())
    sts = []
    nax = 10**6+5
    child = [[0]*26 for _ in range(nax)]
    is_end = [False]*nax
    paths = [[]]*n
    nxt = 1

    for who in range(n):
        s = input()[::-1]
        sts.append(s)
        node = 0
        for ch in s:
            paths[who].append(node)
            nm = ord(ch)-ord("a")
            if child[node][nm] == 0:
                child[node][nm] = nxt
                nxt += 1
            node = child[node][nm]
        is_end[node] = True

    print(node)

    ans = 0
    for who in range(n):
        s = sts[who]
        suffix = set()
        for i in range(len(s)-1,-1,-1):
            suffix.add(s[i])
            node = paths[who][i]
            for ch in suffix:
                ans += is_end[child[node][ord(ch)-ord("a")]]
        print(ans)
    print(ans-n)

    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
N = int(next(sys.stdin))
for S in sys.stdin:
  pass

Submission status: Wrong Answer

Solution code:
N = int(input())
for _ in range(N):
  input()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MASK30 = (1 << 30) - 1
MASK31 = (1 << 31) - 1
MASK61 = (1 << 61) - 1

@njit((i8, ), cache=True)
def rh_modulo(x):
    xu, xd = x >> 61, x & MASK61
    x = xu + xd
    if x >= MASK61:
        x -= MASK61
    return x


@njit((i8, i8), cache=True)
def rh_multiply(a, b):
    au, ad = a >> 31, a & MASK31
    bu, bd = b >> 31, b & MASK31
    x = ad * bu + au * bd
    xu, xd = x >> 30, x & MASK30
    return rh_modulo(au * bu * 2 + xu + (xd << 31) + ad * bd)


@njit((i8, i8), cache=True)
def rh_pows(base, max_len):
    pows = np.empty(max_len, np.int64)
    pows[0] = 1
    for n in range(1, max_len):
        pows[n] = rh_multiply(pows[n - 1], base)
    return pows


@njit((i8[:], i8, i8[:]), cache=True)
def compute_rh(pows, base, S):
    N = len(S)
    RH = np.empty(N, np.int64)
    RH[0] = S[0]
    for n in range(1, N):
        x = rh_multiply(RH[n - 1], base) + S[n]
        if x >= MASK61:
            x -= MASK61
        RH[n] = x
    return RH


@njit((i8[:], i8, i8[:], i8, i8), cache=True)
def rh_substr(pows, base, RH, l, r):
    h = RH[r]
    if l > 0:
        h -= rh_multiply(RH[l], pows[r - l])
    if h < 0:
        h += MASK61
    return h

@njit((i8[:], ), cache=True)
def main(S):
    S = S.copy()
    l_ind = np.where(S == -1)[0][:-1] + 1
    r_ind = np.where(S == -1)[0][1:]
    N = len(l_ind)
    # 逆順にしておく
    for i in range(N):
        S[l_ind[i]:r_ind[i]] = S[l_ind[i]:r_ind[i]][::-1]

    # rolling hashの計算
    max_len = len(S) + 10
    base = np.random.randint(0, 1<<31)
    pows = rh_pows(base, max_len)
    RH = np.zeros_like(S)
    for i in range(N):
        RH[l_ind[i]:r_ind[i]] = compute_rh(pows, base, S[l_ind[i]:r_ind[i]])

    # 後ろ（自身も含む）に置ける文字集合の計算
    sets = np.zeros_like(S)
    for i in range(N):
        for j in range(r_ind[i] - 1, l_ind[i] - 1, -1):
            sets[j] = sets[j + 1] | 1 << S[j]

    # 作れる組 (prefix, 右からの1文字)をすべて計算する
    ptr = 0
    nums = np.empty(len(S) * 26 + 10, np.int64)
    for i in range(N):
        for j in range(l_ind[i], r_ind[i]):
            for k in range(26):
                if sets[j] & 1 << k:
                    h = rh_multiply(RH[j - 1], base) + k
                    nums[ptr] = h
                    ptr += 1
    nums = nums[:ptr]
    nums.sort()
    # 各文字列とマッチングする対象を数える
    ans = 0
    for i in range(N):
        h = rh_multiply(RH[r_ind[i] - 2], base) + S[r_ind[i] - 1]
        cnt = np.searchsorted(nums, h, 'right')
        cnt -= np.searchsorted(nums, h, 'left')
        ans += cnt - 1  # 自分を除外
    print(ans)

N = int(readline())
S = np.array(list(read().rstrip()), np.int64)

S[S == ord('\n')] = -1
S[S > 0] -= ord('a')
S = np.insert(S, 0, -1)
S = np.append(S, -1)

main(S)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
### ローリングハッシュ rolling hash
import random
M = 10**9+7
b = random.choice(range(M))
l = [chr(v) for v in range(ord("a"), ord("z")+1)]
d = {c:i+1 for i,c in enumerate(l)}
def rhash(s):
    ans = 0
    v = 1
    l = len(s)
    vs = [None]*l
    rs = [None]*l
    tmps = [None]*l
    for i in range(l-1, -1, -1):
        ans += d[s[i]]*v
        vs[i] = v
        v *= b
        ans %= M
        v %= M
        rs[i] = ans
        tmps[i] = s[i:]
    rs.append(0)
    tmps.append("")
    tmp = set()
    ss = set()
#     out = set()
    for i in range(l):
        tmp.add(s[i])
        for c in tmp:
            ss.add((rs[i+1] + vs[i]*d[c])%M)
#             out.add(c+tmps[i+1])
    return ss, ans#, out
from collections import defaultdict
dd = defaultdict(list)
ans = 0
rs = [None]*n
for i in range(n):
    ss, rs[i] = rhash(input())
    assert rs[i] in ss
    for item in ss:
        dd[item].append(i)
for i in range(n):
    ans += len(dd[rs[i]])-1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

"""
root = 10000
MODs = [10 ** 9 + 7, 10 ** 9 + 9]
def rolling_hash(s):
    hashes = [[0] * len(s) for _ in range(len(MODs))]
    for hs, MOD in zip(hashes, MODs):
        hs[0] = ord(s[0]) % MOD
        for i in range(1, len(hs)):
            hs[i] += hs[i - 1] * root + ord(s[i])
    return hashes        
"""

root = 10000
MOD = 10 ** 9 + 7
def rolling_hash(s):
    hs = [0] * (len(s) + 1)
    for i in range(len(s)):
        hs[i + 1] = hs[i] * root + ord(s[i]) % MOD
    return hs

N = int(input())
S_list = [input() for _ in range(N)]
S_list.sort(key=len, reverse=True)

ans = 0
counts = defaultdict(int)
for S in S_list:
    alpha_suffix_set = set()
    hash_of_S = rolling_hash(S)
    alpha_set = set()
    for i in range(len(S)):
        alpha_set.add(S[i])
        suffix_hash = (hash_of_S[len(S)] - hash_of_S[i+1] * pow(root, (len(S) - i - 1), MOD)) % MOD
        for alpha in alpha_set:
            alpha_suffix_set.add((alpha, suffix_hash))

    suffix_of_S = (hash_of_S[len(S)] - hash_of_S[1] * pow(root, (len(S) - 1), MOD)) % MOD
    ans += counts[(S[0], suffix_of_S)]
    for elem in alpha_suffix_set:
        counts[elem] += 1
            
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
ss=[input() for i in range(n)]
m=dict()
def chi(x):
    return ord(x)-ord("a")
def cha(x):
    return chr(97+x)
#それぞれの文字列のi文字目までの種類
#set→整数
check=[[0 for j in range(len(ss[i]))]for i in range(n)]
for i in range(n):
    check[i][0]=1<<chi(ss[i][0])
    for j in range(1,len(ss[i])):
        check[i][j]=check[i][j-1]^(1<<chi(ss[i][j]))
#m[s][i]:0or1
for i in range(n):
    if ss[i][1:] not in m:
        m[ss[i][1:]]=[0]*26
        m[ss[i][1:]][chi(ss[i][0])]+=1
    else:
        m[ss[i][1:]][chi(ss[i][0])]+=1
ans=0
for i in range(n):
    s=""
    l=len(ss[i])
    for j in range(l,1,-1):
        if j!=l:
            s=ss[i][j]+s
        for k in range(26):
            if s in m:
                if m[s][k]:
                    if (check[i][j-1]>>k)&1:
                        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

class RollingHash():
    def __init__(self, s):
        length = len(s)
        base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (length + 2)
        self.pow = [1] * (length + 2)

        for i in range(length):
            self.hash[i+1] = (self.hash[i] + s[i]) * base % self.mod
            self.pow[i+1] = self.pow[i] * base % self.mod
        self.pow[length+1] = self.pow[length] * base % self.mod 

    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        return t % self.mod

ss = []
orda = ord("a")
n = int(input())
for _ in range(n):
    ss.append([ord(item) - orda for item in input().rstrip()])
ss.sort(key=lambda x: len(x), reverse=True)

words = dict()
ans = 0
for s in ss:
    word_len = len(s)
    s_rev = s[::-1]
    RH = RollingHash(s_rev)
    rh = RH.get(0, word_len-1)
    if rh in words:
        ans += words[rh][s_rev[-1]]
    initial = set()
    for i, ch in enumerate(s):
        initial.add(ch)
        for key in initial:
            rh = RH.get(0, word_len-i-1)
            if rh in words:
                words[rh][key] += 1
            else:
                words[rh] = [0] * 26
                words[rh][key] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 31) - 1
        self.hash = [0] * (self.length + 2)
        self.pow = [1] * (self.length + 2)

        for i in range(self.length):
            self.hash[i+1] = (self.hash[i] + ord(s[i])) * self.base % self.mod
            self.pow[i+1] = self.pow[i] * self.base % self.mod
        self.pow[self.length+1] = self.pow[self.length] * self.base % self.mod 

    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        return t % self.mod
    
    def get_wsuff(self, l, r, suff):
        hash_suff = (self.hash[r] + ord(suff)) * self.base % self.mod
        t = hash_suff - self.hash[l] * self.pow[r+1-l] % self.mod
        return t % self.mod

ss = []
n = int(input())
for _ in range(n):
    ss.append(input().rstrip())
ss.sort(key=lambda x: len(x), reverse=True)

words = dict()
ans = 0
for s in ss:
    word_len = len(s)
    s_rev = s[::-1]
    RH = RollingHash(s_rev)
    rh = RH.get(0, word_len)
    if rh in words:
        ans += words[rh]
    initial = set()
    for i, ch in enumerate(s):
        initial.add(ch)
        for key in initial:
            rh = RH.get_wsuff(0, word_len-i-1, key)
            if rh in words:
                words[rh] += 1
            else:
                words[rh] = 1
print(ans)

Submission status: Wrong Answer

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

base = 1000
mod = 10**9 + 7

N = int(input())
S = [input().rstrip()[::-1] for _ in range(N)]
S.sort(key=lambda s: -len(s))
cnt = {}
ans = 0
one = [0] * 26
for s in S:
    n = len(s)
    if n == 1:
        ans += one[ord(s[0]) - ord('a')]
        continue
    hashes = [0] * (n - 1)
    hashes[0] = ord(s[0])
    for i in range(1, n - 1):
        hashes[i] = (hashes[i-1] * base + ord(s[i])) % mod
    if hashes[-1] in cnt:
        ans += cnt[hashes[-1]][ord(s[-1]) - ord('a')]
    found = [0] * 26
    found[ord(s[-1]) - ord('a')] = 1
    for i in range(n - 2, 0, -1):
        found[ord(s[i]) - ord('a')] = 1
        if hashes[i-1] not in cnt:
            cnt[hashes[i-1]] = [0] * 26
        for c in range(26):
            cnt[hashes[i-1]][c] += found[c]
    found[ord(s[0]) - ord('a')] = 1
    for c in range(26):
        one[c] += found[c]
print(ans)

Submission status: Wrong Answer

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

base = 27
mod = 10**9 + 7

N = int(input())
S = [input().rstrip()[::-1] for _ in range(N)]
S.sort(key=lambda s: -len(s))
cnt = {}
ans = 0
one = [0] * 26
for s in S:
    n = len(s)
    if n == 1:
        ans += one[ord(s[0]) - ord('a')]
        continue
    hashes = [0] * (n - 1)
    hashes[0] = ord(s[0]) - ord('a') + 1
    for i in range(1, n - 1):
        hashes[i] = (hashes[i-1] * base + ord(s[i]) - ord('a') + 1) % mod
    if hashes[-1] in cnt:
        ans += cnt[hashes[-1]][ord(s[-1]) - ord('a')]
    found = [0] * 26
    found[ord(s[-1]) - ord('a')] = 1
    for i in range(n - 2, 0, -1):
        found[ord(s[i]) - ord('a')] = 1
        if hashes[i-1] not in cnt:
            cnt[hashes[i-1]] = [0] * 26
        for c in range(26):
            cnt[hashes[i-1]][c] += found[c]
    found[ord(s[0]) - ord('a')] = 1
    for c in range(26):
        one[c] += found[c]
print(ans)

Submission status: Wrong Answer

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

base = 1999849216943526259
mod = (1 << 61) - 1

N = int(input())
S = [input().rstrip()[::-1] for _ in range(N)]
S.sort(key=lambda s: -len(s))
cnt = {}
ans = 0
one = [0] * 26
for s in S:
    n = len(s)
    if n == 1:
        ans += one[ord(s[0]) - ord('a')]
        continue
    hashes = [0] * (n - 1)
    hashes[0] = ord(s[0]) - ord('a')
    for i in range(1, n - 1):
        hashes[i] = (hashes[i-1] * base + ord(s[i]) - ord('a')) % mod
    if hashes[-1] in cnt:
        ans += cnt[hashes[-1]][ord(s[-1]) - ord('a')]
    found = [0] * 26
    found[ord(s[-1]) - ord('a')] = 1
    for i in range(n - 2, 0, -1):
        found[ord(s[i]) - ord('a')] = 1
        if hashes[i-1] not in cnt:
            cnt[hashes[i-1]] = [0] * 26
        for c in range(26):
            cnt[hashes[i-1]][c] += found[c]
    found[ord(s[0]) - ord('a')] = 1
    for c in range(26):
        one[c] += found[c]
print(ans)

Submission status: Wrong Answer

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

base = 100
mod = (1 << 61) - 1

N = int(input())
S = [input().rstrip()[::-1] for _ in range(N)]
S.sort(key=lambda s: -len(s))
cnt = {}
ans = 0
one = [0] * 26
for s in S:
    n = len(s)
    if n == 1:
        ans += one[ord(s[0]) - ord('a')]
        continue
    hashes = [0] * (n - 1)
    hashes[0] = ord(s[0]) - ord('a')
    for i in range(1, n - 1):
        hashes[i] = (hashes[i-1] * base + ord(s[i]) - ord('a')) % mod
    if hashes[-1] in cnt:
        ans += cnt[hashes[-1]][ord(s[-1]) - ord('a')]
    found = [0] * 26
    found[ord(s[-1]) - ord('a')] = 1
    for i in range(n - 2, 0, -1):
        found[ord(s[i]) - ord('a')] = 1
        if hashes[i-1] not in cnt:
            cnt[hashes[i-1]] = [0] * 26
        for c in range(26):
            cnt[hashes[i-1]][c] += found[c]
    found[ord(s[0]) - ord('a')] = 1
    for c in range(26):
        one[c] += found[c]
print(ans)

Submission status: Wrong Answer

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

base = 26
mod = (1 << 61) - 1

N = int(input())
S = [input().rstrip()[::-1] for _ in range(N)]
S.sort(key=lambda s: -len(s))
cnt = {}
ans = 0
one = [0] * 26
for s in S:
    n = len(s)
    if n == 1:
        ans += one[ord(s[0]) - ord('a')]
        continue
    hashes = [0] * (n - 1)
    hashes[0] = ord(s[0]) - ord('a')
    for i in range(1, n - 1):
        hashes[i] = (hashes[i-1] * base + ord(s[i]) - ord('a')) % mod
    if hashes[-1] in cnt:
        ans += cnt[hashes[-1]][ord(s[-1]) - ord('a')]
    found = [0] * 26
    found[ord(s[-1]) - ord('a')] = 1
    for i in range(n - 2, 0, -1):
        found[ord(s[i]) - ord('a')] = 1
        if hashes[i-1] not in cnt:
            cnt[hashes[i-1]] = [0] * 26
        for c in range(26):
            cnt[hashes[i-1]][c] += found[c]
    found[ord(s[0]) - ord('a')] = 1
    for c in range(26):
        one[c] += found[c]
print(ans)