Problem:


Score : 700 points

Problem Statement

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

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

Constraints

2 \leq N \leq 200\,000

S_i consists of lowercase English letters a-z.

S_i \neq S_j

1 \leq |S_i|

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

Input

Input is given from Standard Input in the following format.

N
S_1
S_2
\vdots
S_N

Output

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

Sample Input 1

3
abcxyx
cyx
abc

Sample Output 1

1

The only good pair is (abcxyx, cyx).

Sample Input 2

6
b
a
abc
c
d
ab

Sample Output 2

5

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



Sample input:
3
abcxyx
cyx
abc


Sample output:
1

Submission status: Time Limit Exceeded

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


class RollingHash:
    """文字列stringsの部分文字列のハッシュを構築する。O(N)"""
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MASK30 = (1 << 30) - 1
        self.MASK31 = (1 << 31) - 1
        self.MASK61 = (1 << 61) - 1
        self.MOD = self.MASK61
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)

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

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

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

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

    def merge(self, h1, h2, length2):
        """ハッシュ値h1と長さlength2のハッシュ値h2を結合する。O(1)"""
        return self.calc_mod(self.mul(h1, self.pow[length2]) + h2)

    def get_lcp(self, l1, r1, l2, r2):
        """string[l1:r2]とstring[l2:r2]の長共通接頭辞(Longest Common Prefix)の
        長さを求める。O(log|string|)
        """
        ng = min(r1 - l1, r2 - l2) + 1
        ok = 0
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if self.get_hash(l1, l1 + mid) == self.get_hash(l2, l2 + mid):
                ok = mid
            else:
                ng = mid
        return ok


n = int(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]  # stringの後ろから見る
    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]:
        h_str = rh.get_hash(0, r - 1)
        h_r = rh.get_hash(r - 1, r)
        set_char.add(h_r)
        for h1 in set_char:
            if h1 == h_r:
                continue
            h = rh.merge(h_str, h1, 1)
            if h in str_set:
                cnt += 1
    str_set.add(rh.get_hash(0, n))

print(cnt)

Submission status: Time Limit Exceeded

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


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

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

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

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

    def get_hash(self, l, r):
        """string[l:r]のハッシュ値を返す。O(1)"""
        res = (self.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: Time Limit Exceeded

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


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

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


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

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


class RollingHash:
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 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] + 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: Time Limit Exceeded

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, ALPHABET_SIZE):
		self.char = char
		self.children = [-1] * ALPHABET_SIZE
		self.flag = [0] * ALPHABET_SIZE

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

	def _convert_char_to_num(self, char):
		return ord(char) - ord('a')

	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 current.children[char_index] != -1:
				current = current.children[char_index]

			else:
				new_node = Node(char, ALPHABET_SIZE)
				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: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    ans = 0
    Ss = []
    orda = ord('a')
    for _ in range(N):
        S = list(input().rstrip())
        Ss.append(list(map(lambda c:ord(c)-orda, reversed(S))))
    Ss.sort(key=lambda x:len(x))
    
    ctkey = 26
    RTrie = [0]*52
    for i in range(N):
        S = Ss.pop()
        charct = Counter(S)
        node = RTrie
        L = len(S)
        for i, c in enumerate(S):
            if i == L-1:
                ans += node[ctkey+c]
            for a in charct.keys():
                node[ctkey+a] += 1
            charct[c] -= 1
            if charct[c] == 0:
                del charct[c]
            if not node[c]:
                node[c] = [0]*52
            node = node[c]
    
    print(ans)

main()

Submission status: Time Limit Exceeded

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] *= 26
        rollinghash[i] += ord(S[i][j]) - 97
        rollinghash[i] &= mod
        se[rollinghash[i]].add(i)
    j -= 1
print(ans)

Submission status: Time Limit Exceeded

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

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

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
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
        se[rollinghash[i]].add(i)
    j -= 1
print(ans)

Submission status: Time Limit Exceeded

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

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

BASE, MOD = 1999849216943526259, (1<<61)-1

d = dict()
ans = 0
ss = [input()[::-1] for _ in range(int(input()))]
zero = [0 for _ in range(26)]
ss.sort(key=lambda x: -len(x))
for s in ss:
	n = len(s)
	if n == 1:
		ans += zero[ord(s[n-1])-97]
	else:
		hashes = [0 for _ in range(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[n-2] in d:
			ans += d[hashes[n-2]][ord(s[n-1])-97]
		alph = [0 for _ in range(26)]
		alph[ord(s[n-1])-97] = 1
		for i in range(n-2, 0, -1):
			alph[ord(s[i])-97] = 1
			if hashes[i-1] not in d:
				d[hashes[i-1]] = [0 for _ in range(26)]
			for j, a in enumerate(alph):
				d[hashes[i-1]][j] += a
		alph[ord(s[0])-97] = 1
		for j, a in enumerate(alph):
			zero[j] += a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

def main():
    N = int(next(sys.stdin))
    root = {'val': {}}
    r = 0
    SS = []
    for S in sys.stdin:
        C = Counter(S)
        d = root
        for s in reversed(S):
            val = d['val']
            for c in C.keys():
                val[c] = val.get(c, 0) + 1
            C[s] -= 1
            if C[s] == 0:
                del C[s]
            if s not in d:
                d[s] = {'val': {}}
            d = d[s]
        SS.append((val, S[0]))
    return sum(v[k] for v, k in SS) - N

print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import islice

def main():
    N = int(input())
    root = {'val': {}}
    r = 0
    SS = []
    for _ in range(N):
        S = input()
        SS.append(S)
        C = Counter(S)
        d = root
        for s in reversed(S):
            val = d['val']
            for c in C.keys():
                val[c] = val.get(c, 0) + 1
            C[s] -= 1
            if C[s] == 0:
                del C[s]
            if s not in d:
                d[s] = {'val': {}}
            d = d[s]

    for S in SS:
        d = root
        for s in islice(reversed(S), len(S) - 1):
            d = d[s]
        r += d['val'][S[0]] - 1
    return r

print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():
    N = int(input())
    root = {'val': {}}
    r = 0
    SS = []
    for _ in range(N):
        SS.append(input()[::-1])
    for S in SS:
        C = Counter(S)
        d = root
        for s in S:
            val = d['val']
            for k, v in C.items():
                val[k] = val.get(k, 0) + 1
            C[s] -= 1
            if C[s] == 0:
                del C[s]
            if s not in d:
                d[s] = {'val': {}}
            d = d[s]
    for S in SS:
        d = root
        for s in S[:-1]:
            d = d[s]
        r += d['val'][S[-1]] - 1
    return r

print(main())

Submission status: Time Limit Exceeded

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 = dict()
    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
                    if h in nums:
                        nums[h] += 1
                    else:
                        nums[h] = 1
    # 各文字列とマッチングする対象を数える
    ans = 0
    for i in range(N):
        h = rh_multiply(RH[r_ind[i] - 2], base) + S[r_ind[i] - 1]
        ans += nums[h] - 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: Time Limit Exceeded

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 = nums[np.argsort(nums, kind='mergesort')]
    # 各文字列とマッチングする対象を数える
    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: Time Limit Exceeded

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 = (1 << 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)]
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: Time Limit Exceeded

Solution code:
from collections import defaultdict

n = int(input())

ss = [input() for _ in range(n)]

ss.sort(key=len)

ans = 0
m0 = set()
m = defaultdict(lambda: set())
ml = {}
ls = set()

for s in ss:
    ans += len(m0 & set(s))
    s1 = s[1:]
    l = len(s1)
    if l == 0:
        m0.add(s)
        continue

    si = set(s[-i:] for i in ls)
    for k in m.keys() & si:
        ans += len(m[k] & set(s[:-ml[k]]))

    m[s1].add(s[0])
    ml[s1] = l
    ls.add(l)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n = int(input())

ss = [input() for _ in range(n)]

ss.sort(key=len)

ans = 0
m0 = set()
m = defaultdict(lambda : set())
ls = set()

for s in ss:
    ans += len(m0 & set(s))
    l = len(s[1:])
    if l == 0:
        m0.add(s)
        continue

    for i in ls:
        if s[-i:] in m:
            ans += len(m[s[-i:]] & set(s[:-i]))

    m[s[1:]].add(s[0])
    ls.add(l)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n = int(input())

ss = [input() for _ in range(n)]

ss.sort(key=len)

ans = 0
m0 = set()
m = defaultdict(lambda : set())
ml = 0
for s in ss:
    ans += len(m0 & set(s))
    l = len(s[1:])
    if l == 0:
        m0.add(s)
        continue

    b = set(s[-i:] for i in range(1, ml+1))
    for k in b & m.keys():
        ans += len(m[k] & set(s[:-len(k)]))

    m[s[1:]].add(s[0])
    ml = l

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n = int(input())

ss = [input() for _ in range(n)]

ss.sort(key=len)

ans = 0
m0 = set()
m = defaultdict(lambda : set())
ml = 0
for s in ss:
    ans += len(m0 & set(s))
    l = len(s[1:])
    if l == 0:
        m0.add(s)
        continue

    for i in range(1, ml+1):
        if s[-i:] in m:
            ans += len(m[s[-i:]] & set(s[:-i]))

    m[s[1:]].add(s[0])
    ml = l

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ss=[input() for i in range(n)]
m=dict()
def chi(x):
    return ord(x)-ord("a")
#それぞれの文字列の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
#mapも整数に(あるかどうかなので)
for i in range(n):
    if ss[i][1:] not in m:
        m[ss[i][1:]]=0
    m[ss[i][1:]]|=1<<chi(ss[i][0])
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)&1:
                    if (check[i][j-1]>>k)&1:
                        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

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)