Problem:


Score : 700 points

Problem Statement

Limak can repeatedly remove one of the first two characters of a string,
    for example abcxyx \rightarrow acxyx \rightarrow cxyx \rightarrow cyx.

You are given N different strings S_1, S_2, \ldots, S_N.
Among N \cdot (N-1) / 2 pairs (S_i, S_j),
    in how many pairs could Limak obtain one string from the other?

Constraints

2 \leq N \leq 200\,000

S_i consists of lowercase English letters a-z.

S_i \neq S_j

1 \leq |S_i|

|S_1| + |S_2| + \ldots + |S_N| \leq 10^6

Input

Input is given from Standard Input in the following format.

N
S_1
S_2
\vdots
S_N

Output

Print the number of unordered pairs (S_i, S_j)
    where i \neq j and Limak can obtain one string from the other.

Sample Input 1

3
abcxyx
cyx
abc

Sample Output 1

1

The only good pair is (abcxyx, cyx).

Sample Input 2

6
b
a
abc
c
d
ab

Sample Output 2

5

There are five good pairs: (b, abc), (a, abc), (abc, c), (b, ab), (a, ab).



Sample input:
3
abcxyx
cyx
abc


Sample output:
1

Submission status: Accepted

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


class RollingHash:
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = 67280421310721
        # (2 << 61) - 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] * self.BASE + ord(char)) % 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] * rh.BASE + ord(char)) % rh.MOD
            if h in str_set:
                cnt += 1
    str_set.add(rh.get_hash(0, n))

print(cnt)

Submission status: Accepted

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


class RollingHash:
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = 92709568269121
        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] * self.BASE + ord(char)) % 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] * rh.BASE + ord(char)) % rh.MOD
            if h in str_set:
                cnt += 1
    str_set.add(rh.get_hash(0, n))

print(cnt)

Submission status: Accepted

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


class RollingHash:
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 51) - 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: Accepted

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


class RollingHash:
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 45) - 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: Accepted

Solution code:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
# from collections import defaultdict
ALPHABET_SIZE = 26

def getlist():
	return list(map(int, input().split()))

class Node(object):
	def __init__(self, char):
		self.char = char
		self.children = {}
		self.flag = [0] * ALPHABET_SIZE

class Trie(object):
	def __init__(self):
		self.root = Node(' ')

	def _convert_char_to_num(self, char):
		return ord(char) - 97

	def insert(self, word, tail):
		res = 0 #合う値
		current = self.root
		currentFlag = [0] * ALPHABET_SIZE

		for char in word:
			char_index = self._convert_char_to_num(char)
			for i in range(ALPHABET_SIZE):
				currentFlag[i] += current.flag[i]
			res += currentFlag[char_index]
			currentFlag[char_index] = 0

			if char_index in current.children:
				current = current.children[char_index]

			# if current.children[char_index] != -1:
			# 	current = current.children[char_index]
			else:
				new_node = Node(char)
				current.children[char_index] = new_node
				current = new_node

		char_index = self._convert_char_to_num(tail)
		res += currentFlag[char_index]

		current.flag[self._convert_char_to_num(tail)] += 1

		return res

#処理内容
def main():
	N = int(input())
	L = []
	for i in range(N):
		S = input()[::-1]
		L.append([len(S), S])

	L.sort(key = lambda x:x[0])

	ans = 0
	trie = Trie()
	for val, s in L:
		s1 = s[:-1]
		tail = s[-1]
		ans += trie.insert(s1, tail)
		# print(ans)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

# trie作成パート
# nodeはnode番号を表す
# pathに各々の単語に相当するnodeの列を格納
# childはそのノードの次に行くノードを記録していく
# is_endでそのnodeで終わるものが有るかどうかをcheck
# 最終的にはもう一度見直してis_endがtrue担っている場所を数えて
# 元々、その単語自体がそこで終わっているのがn通り有るので減算して提出
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 = set()
    nagasa = len(word)
    for j in range(nagasa - 1, -1, -1):
        kouho.add(word[j])
        node = paths[i][j]
        for s in kouho:
            num = ord(s) - a
            ans += is_end[child[node][num]]
print(ans - n)

Submission status: Accepted

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 = [[] for i in range(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

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

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

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]

    # Trie木の構築
    path = np.zeros_like(S)
    child = np.zeros((len(S), 26), np.int64)
    is_end = np.zeros(len(S), np.bool_)

    n_node = 1
    for i in range(N):
        node = 0
        for j in range(l_ind[i], r_ind[i]):
            path[j] = node
            if child[node][S[j]] == 0:
                child[node][S[j]] = n_node
                n_node += 1
            node = child[node][S[j]]
        is_end[node] = True
    child = child[:n_node]
    is_end = is_end[:n_node]
    ans = 0
    for i in range(N):
        se = 0
        for j in range(r_ind[i] - 1, l_ind[i] - 1, -1):
            se |= 1 << S[j]
            node = path[j]
            for k in range(26):
                if se & 1 << k:
                    if is_end[child[node][k]]:
                        ans += 1
    return ans - N

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba import njit, b1, i4, i8, f8
    import numba
    from numba.pycc import CC
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc_export(main, (i8[:],))
    cc.compile()

from my_module import main

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)

print(main(S))

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

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]

    # Trie木の構築
    path = np.zeros_like(S)
    child = np.zeros((len(S), 26), np.int64)
    is_end = np.zeros(len(S), np.bool_)

    n_node = 1
    for i in range(N):
        node = 0
        for j in range(l_ind[i], r_ind[i]):
            path[j] = node
            if child[node][S[j]] == 0:
                child[node][S[j]] = n_node
                n_node += 1
            node = child[node][S[j]]
        is_end[node] = True
    child = child[:n_node]
    is_end = is_end[:n_node]
    ans = 0
    for i in range(N):
        se = 0
        for j in range(r_ind[i] - 1, l_ind[i] - 1, -1):
            se |= 1 << S[j]
            node = path[j]
            for k in range(26):
                if se & 1 << k:
                    if is_end[child[node][k]]:
                        ans += 1
    return ans - N

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba import njit, b1, i4, i8, f8
    import numba
    from numba.pycc import CC
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc_export(main, (i8[:],))
    cc.compile()

from my_module import main

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)

print(main(S))

Submission status: Accepted

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

@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]

    # Trie木の構築
    path = np.zeros_like(S)
    child = np.zeros((len(S), 26), np.int64)
    is_end = np.zeros(len(S), np.bool_)

    n_node = 1
    for i in range(N):
        node = 0
        for j in range(l_ind[i], r_ind[i]):
            path[j] = node
            if child[node][S[j]] == 0:
                child[node][S[j]] = n_node
                n_node += 1
            node = child[node][S[j]]
        is_end[node] = True
    child = child[:n_node]
    is_end = is_end[:n_node]
    ans = 0
    for i in range(N):
        se = 0
        for j in range(r_ind[i] - 1, l_ind[i] - 1, -1):
            se |= 1 << S[j]
            node = path[j]
            for k in range(26):
                if se & 1 << k:
                    if is_end[child[node][k]]:
                        ans += 1
    return ans - N

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)

print(main(S))

Submission status: Accepted

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] + 10
    for n in range(1, N):
        x = rh_multiply(RH[n - 1], base) + S[n] + 10
        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)
    base = 1000
    pows = rh_pows(base, max_len)
    RH = np.zeros_like(S)
    full_RH = np.empty(N, np.int64)
    for i in range(N):
        RH[l_ind[i]:r_ind[i]] = compute_rh(pows, base, S[l_ind[i]:r_ind[i]])
        full_RH[i] = RH[r_ind[i] - 1]
    # 後ろ（自身も含む）に置ける文字集合の計算
    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]

    full_RH.sort()

    # 作れる組 (prefix, 右からの1文字)をすべて計算する
    ans = 0
    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 + 10
                    cnt = np.searchsorted(full_RH, h, 'right')
                    cnt -= np.searchsorted(full_RH, h, 'left')
                    ans += cnt
    ans -= N
    return 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)

print(main(S))

Submission status: Accepted

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] + 10
    for n in range(1, N):
        x = rh_multiply(RH[n - 1], base) + S[n] + 10
        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: Accepted

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] + 10
    for n in range(1, N):
        x = rh_multiply(RH[n - 1], base) + S[n] + 10
        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: Accepted

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

class Trie:
    class Node:
        def __init__(self):
            self.nxt = [-1] * 26
            self.is_end = False

    def __init__(self, N):
        self.nodes = [self.Node()]
        self.paths = [[] for _ in range(N)]

    def add(self, s, i):
        node = 0
        for c in s:
            c = ord(c) - ord('a')
            self.paths[i].append(node)
            if self.nodes[node].nxt[c] == -1:
                self.nodes[node].nxt[c] = len(self.nodes)
                self.nodes.append(self.Node())
            node = self.nodes[node].nxt[c]
        self.nodes[node].is_end = True

    def query(self, s, i):
        ret = 0
        suffix = set()
        for j in range(len(s) - 1, -1, -1):
            suffix.add(ord(s[j]) - ord('a'))
            node = self.paths[i][j]
            for c in suffix:
                if self.nodes[node].nxt[c] != -1:
                    ret += self.nodes[self.nodes[node].nxt[c]].is_end
        return ret

N = int(input())
S = [input().rstrip()[::-1] for _ in range(N)]
trie = Trie(N)
ans = 0
for i, s in enumerate(S):
    trie.add(s, i)
for i, s in enumerate(S):
    ans += trie.query(s, i)
print(ans - N)

Submission status: Accepted

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

class Node:
    def __init__(self):
        self.nxt = [-1] * 26
        self.is_end = False

nodes = [Node()]
N = int(input())
S = [input().rstrip()[::-1] for _ in range(N)]
S.sort(key=lambda s: len(s))
ans = 0
for i, s in enumerate(S):
    path = []
    node = 0
    for c in s:
        c = ord(c) - ord('a')
        path.append(node)
        if nodes[node].nxt[c] == -1:
            nodes[node].nxt[c] = len(nodes)
            nodes.append(Node())
        node = nodes[node].nxt[c]
    nodes[node].is_end = True

    suffix = set()
    for j in range(len(s) - 1, -1, -1):
        suffix.add(ord(s[j]) - ord('a'))
        node = path[j]
        for c in suffix:
            if nodes[node].nxt[c] != -1:
                ans += nodes[nodes[node].nxt[c]].is_end
print(ans - N)

Submission status: Accepted

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

class Node:
    def __init__(self):
        self.nxt = [-1] * 26
        self.is_end = False

nodes = [Node()]
N = int(input())
S = [input().rstrip()[::-1] for _ in range(N)]
paths = [[] for _ in range(N)]
for i, s in enumerate(S):
    node = 0
    for c in s:
        c = ord(c) - ord('a')
        paths[i].append(node)
        if nodes[node].nxt[c] == -1:
            nodes[node].nxt[c] = len(nodes)
            nodes.append(Node())
        node = nodes[node].nxt[c]
    nodes[node].is_end = True

ans = 0
for i, s in enumerate(S):
    suffix = set()
    for j in range(len(s) - 1, -1, -1):
        suffix.add(ord(s[j]) - ord('a'))
        node = paths[i][j]
        for c in suffix:
            if nodes[node].nxt[c] != -1:
                ans += nodes[nodes[node].nxt[c]].is_end
print(ans - N)

Submission status: Accepted

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

M = 10**6
child = [[0] * 26 for _ in range(M)]
is_end = [False] * M
nxt = 1

N = int(input())
S = [input().rstrip()[::-1] for _ in range(N)]
paths = [[] for _ in range(N)]
for i, s in enumerate(S):
    node = 0
    for c in s:
        c = ord(c) - ord('a')
        paths[i].append(node)
        if child[node][c] == 0:
            child[node][c] = nxt
            nxt += 1
        node = child[node][c]
    is_end[node] = True

ans = 0
for i, s in enumerate(S):
    suffix = set()
    for j in range(len(s) - 1, -1, -1):
        suffix.add(ord(s[j]) - ord('a'))
        node = paths[i][j]
        for c in suffix:
            ans += is_end[child[node][c]]
print(ans - N)

Submission status: Accepted

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

def empty_list():
    return [0] * 26

class RollingHash():
    def __init__(self, s):
        length = len(s)
        base = 1009
        # self.mod = (1 << 61) - 1
        self.mod = 67280421310721
        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 = []
n = int(input())
for _ in range(n):
    ss.append([ord(item) for item in input().rstrip()])
ss.sort(key=lambda x: len(x), reverse=True)

orda = ord("a")
words = defaultdict(empty_list)
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)
    ans += words[rh][s_rev[-1] - orda]
    initial = [0] * 26 
    for i, ch in enumerate(s):
        initial[ch - orda] = 1
        for j, is_initial in enumerate(initial):
            if is_initial:
                rh = RH.get(0, word_len-i-1)
                words[rh][j] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class RollingHash(object):
    _base1, _base2 = 1007, 1009
    _mod1, _mod2 = 10**9 + 9, 10**9 + 7

    def __init__(self,s):
        self._n=len(s)
        H1, H2 = [0] * (self._n + 1), [0] * (self._n + 1)
        P1, P2 = [1] * (self._n + 1), [1] * (self._n + 1)
        for i in range(self._n):
            H1[i + 1] = (H1[i] * self._base1 + ord(s[i])) % self._mod1
            H2[i + 1] = (H2[i] * self._base2 + ord(s[i])) % self._mod2
            P1[i + 1] = P1[i] * self._base1 % self._mod1
            P2[i + 1] = P2[i] * self._base2 % self._mod2
        self._H1, self._H2 = H1, H2
        self._P1, self._P2 = P1, P2

    def __len__(self):
        return self._n

    def __getitem__(self,x):
        l, r = x.start, x.stop;
        return ((self._H1[r] - self._P1[r - l] * self._H1[l] % self._mod1) % self._mod1,
                (self._H2[r] - self._P2[r - l] * self._H2[l] % self._mod2) % self._mod2)

from collections import defaultdict
def resolve():
    n = int(input())
    X = [input() for _ in range(n)]
    X.sort(key = len, reverse = 1)

    count = defaultdict(lambda:[0] * 26)
    ans = 0

    for S in X:
        k = len(S)
        rh = RollingHash(S)
        ok = [False] * 26
        ans += count[rh[1 : k]][ord(S[0]) - ord('a')]
        for i, c in enumerate(S):
            ok[ord(c) - ord('a')] = True
            for j in range(26):
                if ok[j]:
                    count[rh[i + 1 : k]][j] += 1
    print(ans)
resolve()

Submission status: Accepted

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

base = 30
mod = 10**17 + 3

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)