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

Solution (Python):
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]  
    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)

Solution (Python):
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.calc_mod(self.hash[r] - self.mul(self.hash[l], self.pow[r - l]))
        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.calc_mod(rh.mul(rh.hash[r - 1], rh.BASE) + ord(char))
            if h in str_set:
                cnt += 1
    str_set.add(rh.get_hash(0, n))

print(cnt)

Solution (Python):
import sys
input = sys.stdin.readline


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

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):



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]

			
			
			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)

if __name__ == '__main__':
	main()

Solution (Python):
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 = 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)

Solution (Python):
'''
自宅用PCでの解答
https://atcoder.jp/contests/agc047/editorial/43を参考にpythonで実装
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


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

Solution (Python):
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)

Solution (Python):
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]

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

Solution (Python):
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]

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

Solution (Python):
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]

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

Solution (Python):
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]

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

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

Solution (Python):
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]

    
    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]

    
    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)

Solution (Python):
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]

    
    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]

    
    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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)