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
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): 
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f
import random
class rh:
    def __init__(self,base,max_n):
        self.mod=random.randrange(1<<54-1,1<<55-1,2)
        self.base=int(base*0.5+0.5)*2
        self.max_n=max_n
        self.pows1=[1]*(max_n+1)
        cur1=1
        for i in range(1,max_n+1):
            cur1=cur1*base%self.mod
            self.pows1[i]=cur1

    def convert(self,c): return alp2num(c,False)
    
    def get(self, s):
        n=len(s)
        mod=self.mod
        si=[self.convert(ss) for ss in s]
        h1=0
        for i in range(n):h1=(h1+si[i]*self.pows1[n-1-i])%mod
        return h1
    
    def get_roll(self, s, k, uroboros=False):
        
        n=len(s)
        maxitr=n-k+1
        if uroboros: maxitr=n
    
        si=[self.convert(ss) for ss in s]
        mod=self.mod
        h1=0
        for i in range(k):h1=(h1+si[i%n]*self.pows1[k-1-i])%mod
        hs=[0]*maxitr
        hs[0]=h1
        mbase1=self.pows1[k]
        base=self.base
        
        for i in range(1,maxitr): 
            front=si[i-1];back=si[(i+k-1)%n]
            h1=(h1*base-front*mbase1+back)%mod
            hs[i]=h1
        return hs

def main():
    mod = 1000000007
    

    N = int(input())
    mod=1000000007
    mod2=999999937

    
    
    L=["" for _ in range(N)]
    ll=[0]*N
    for i in range(N):
        s=input()
        ls=len(s)
        ll[i]=ls
        L[i]=s

    

    inds=argsort(ll)
    d=Counter()
    ans=0
    base=27

    for im in inds:
        
        s=L[im]

        ls=len(s)
        cur=0
        cur2=0
        se=Counter(s)
        
        for i in range(ls):
            for a,val in se.items():
                if val:
                    ai=alp2num(a)
                    ans+=d[(i+1,(cur*base+ai)%mod,(cur2*base+ai)%mod2)]
                    
            si=s[-1-i]
            sin=alp2num(si)
            cur=(cur*base+sin)%mod
            cur2=(cur2*base+sin)%mod2

            se[si]-=1

        d[(ls,cur,cur2)]+=1

    print(ans)
            





if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter

n = int(input())
sss = [input() for _ in range(n)]
d = {s[1:]: 0 for s in sss}
flags = [1 << (i * 18) for i in range(26)]

trie_chr = [-1]
trie_children = [{}]
trie_counter = [0]
trie_fin = [0]
s_fin_node = []
l = 1

for s in sss:
    node = 0
    trie_counter[node] += 1
    for i in range(len(s) - 1, 0, -1):
        c = ord(s[i]) - 97
        if c in trie_children[node]:
            node = trie_children[node][c]
            trie_counter[node] += 1
        else:
            trie_chr.append(c)
            trie_children.append({})
            trie_fin.append(0)
            trie_children[node][c] = l
            trie_counter.append(1)
            node = l
            l += 1
    trie_fin[node] += 1
    s_fin_node.append(node)

trie_flags = [0] * l

for s in sss:
    cnt = Counter(s)
    flag = 0
    for c in cnt:
        flag |= flags[ord(c) - 97]
    node = 0
    if len(s) > 1 and trie_fin[node] > 0:
        trie_flags[node] += flag

    for i in range(len(s) - 1, 1, -1):
        c = s[i]
        k = ord(c) - 97
        cnt[c] -= 1
        if cnt[c] == 0:
            flag ^= flags[k]

        node = trie_children[node][k]
        
        if trie_counter[node] == 1:
            break
        if trie_fin[node] > 0:
            trie_flags[node] += flag
            







ans = 0
mask = (1 << 18) - 1
for i, s in enumerate(sss):
    cnt = (trie_flags[s_fin_node[i]] >> ((ord(s[0]) - 97) * 18)) & mask
    ans += cnt

print(ans)

Solution (Python):

class TN(object):
	def __init__(self):
		self.h = {}
		self.count = 0
		self.need = collections.Counter()


ais = [raw_input() for _ in range(int(raw_input()))]
ais.sort(key = len)
import collections
cc = collections.Counter()

ans = 0
root = TN()
for w in ais:
	
	
	cur =  root
	for j in range(len(w)-1, -1, -1):
		for k in cur.need:
			if k in w[:j+1]:
				ans += cur.need[k]
		if w[j] in cur.h:
			cur = cur.h[w[j]]
		else:
			break
	
	cur = root
	for j in range(len(w) - 1, 0, -1):
		if w[j] not in cur.h:
			cur.h[w[j]] = TN()
		cur = cur.h[w[j]]
	cur.need[w[0]] += 1

print ans

Solution (Python):
mod1 = 1000000007
mod2 = 1000000009
base1 = 2009
base2 = 1007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    S = []
    for _ in range(N):
        s = input().rstrip('\n')
        S.append(s[::-1])

    S.sort(key=lambda s: len(s), reverse=True)
    cnt = []
    for s in S:
        c = [0] * 26
        for ss in s:
            c[ord(ss) - 97] += 1
        cnt.append(c)
    ans = 0
    H1 = [0] * N
    H2 = [0] * N
    for L in range(1, 10**6+1):
        if not S:
            break
        M = len(S)
        key = []
        i = M-1
        dic_last = {}
        while i >= 0:
            if len(S[i]) == L:
                s = S.pop()
                cnt.pop()
                h1 = H1.pop()
                h2 = H2.pop()
                if L > 1:
                    last = ord(s[L-2]) - 97
                    h1 = (h1 * base1 + last)%mod1
                    h2 = (h2 * base2 + last)%mod2
                key.append((s, h1, h2))
            else:
                if L > 1:
                    ss = ord(S[i][L-2]) - 97
                    cnt[i][ss] -= 1
                    H1[i] = (H1[i] * base1 + ss)%mod1
                    H2[i] = (H2[i] * base2 + ss)%mod2
                    hh = H1[i] * (mod2+1) + H2[i]
                    if hh not in dic_last:
                        dic_last[hh] = [0] * 26
                    for j in range(26):
                        if cnt[i][j] > 0:
                            dic_last[hh][j] += 1
            i -= 1
        for s, h1, h2 in key:
            last = ord(s[-1]) - 97
            h = h1 * (mod2+1) + h2
            if L == 1:
                for i in range(len(cnt)):
                    if cnt[i][last] > 0:
                        ans += 1
            else:
                if h in dic_last:
                    ans += dic_last[h][last]
        
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math, time
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def LIF(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def SR(n):
    res = [None] * n
    for i in range(n):
        res[i] = S()
    return res
def LSR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LS()
    return res
mod = 1000000007
inf = float('INF')

def solve():
    n = II()
    s = [None] * n
    dp = [None] * n
    for i in range(n):
        dp[i] = [-1] * 26
        s[i] = [input().rstrip()[::-1], i]
    for i in range(n):
        si,_ = s[i]
        dpi = dp[i]
        for j in range(len(si)):
            x = ord(si[j]) - ord("a")
            dpi[x] = j
    d = [s]
    ans = 0
    for i in range(10 ** 6):
        nd = []
        if not d: break
        for lis in d:
            tmp = [[] for i in range(26)]
            for l, k in lis:
                p = ord(l[i]) - ord("a")
                if len(l) == i + 1:
                    for x, m in lis:
                        if k != m:
                            if dp[m][p] >= i:
                                ans += 1
                else:
                    tmp[p].append((l, k))
            for k in tmp:
                if k:
                    nd.append(k)
        d = nd
    print(ans)
    return

if __name__ == '__main__':
    solve()

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

ans = 0
def scomp(S):
    L = 1+max(S)
    table = [0]*L
    for s in S:
        table[s] += 1
    it = [None]*L
    cnt = 0
    for i in range(L):
        it[i] = cnt
        if table[i]:
            cnt += 1
    return it

import sys
readline = sys.stdin.readline

class Node:
    def __init__(self, sigma, depth):
        self.end = False
        self.child = [None] * sigma
        self.depth = depth
        self.count = [0]*sigma
        self.par = None
    def __setitem__(self, i, x):
        self.child[i] = x
    def __getitem__(self, i):
        return self.child[i]

class Trie():
    def __init__(self, sigma):
        self.sigma = sigma
        self.root = Node(sigma, 0)
    
    def add(self, S):
        vn = self.root
        for cs in S:
            if vn[cs] is None:
                vn[cs] = Node(self.sigma, vn.depth + 1)
                vn[cs].par = vn
            vn = vn[cs]
        vn.end = True
    
    def up(self, S):
        vn = self.root
        for cs in S:
            if vn[cs] is None:
                vn[cs] = Node(self.sigma, vn.depth + 1)
            vn = vn[cs]

        k = [0]*self.sigma
        ls = len(S)
        for i in range(ls-1, -1, -1):
            vn = vn.par
            s = S[i]
            k[s] = 1
            for i in range(self.sigma):
                vn.count[i] += k[i]
    
    def count(self, S, ss):
        vn = self.root
        for cs in S:
            if vn[cs] is None:
                vn[cs] = Node(self.sigma, vn.depth + 1)
            vn = vn[cs]
        
        global ans
        ans += vn.count[ss]

ans = 0



N = int(readline())
A = [list(map(lambda x: ord(x)-97, readline().strip()))[::-1] for _ in range(N)]

T = Trie(26)

for a in A:
    T.add(a)
for a in A:
    T.up(a)
for a in A:
    s = a[:-1]
    t = a[-1]
    T.count(s, t)

print(ans-N)

Solution (Python):
from collections import defaultdict
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

N = int(input())
Slist = []
for i in range(N):
    S = input()
    Slist.append(S)
Slist.sort(key=len)
dic = defaultdict(lambda:defaultdict(int))
ans = 0
for S in Slist:
    alp = set()
    l = len(S)
    RH = RollingHash(S,37,10**18+9)
    for i in range(len(S)):
        alp.add(S[i])
        alpdic = dic[RH.get(i+1,l)]
        for X in alpdic.keys():
            if X in alp:
                ans += alpdic[X]
    dic[RH.get(1,l)][S[0]] += 1
print(ans)

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y



def solve(L):
    L = [tuple(ord(c)-ord('a') for c in reversed(s)) for s in L]
    trie = ([None]*26, [])

    for s in L:
        node = trie
        for c in s[:-1]:
            leaf,_ = node
            if leaf[c] is None:
                leaf[c] = ([None]*26, [])
            node = leaf[c]
        node[1].append(s[-1])
    
    cnt = 0
    for s in L:

        app = [0]*26
        for c in s:
            app[c] += 1

        node = trie
        for c in s:
            if node is None:
                break
            leaf,tail = node
            for d in tail:
                if app[d] > 0:
                    cnt += 1
            app[c] -= 1
            node = leaf[c]
    return cnt - len(L)




if __name__ == '__main__':
    N = int(readline())
    L = [s.decode().rstrip() for s in read().split()]
    print(solve(L))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
mod = 10**23 + 117

d = {}

S = [input()[:-1] for i in range(n)]

S.sort(key = lambda x:len(x))

ans = 0
for s in S:
    if len(s) == 1:
        if -1 in d.keys():
            array = d[-1]
            ans += array[ord(s) - ord("a")]
        else: d[-1] = [0]*26
        d[-1][ord(s) - ord("a")] += 1
    else:
        h = 0
        cnt = [0]*26
        for t in s:
            cnt[ord(t) - ord("a")] += 1
        if -1 in d.keys():
            array = d[-1]
            for i in range(26):
                if cnt[i] > 0 and array[i] > 0:ans += 1
        for t in s[len(s) - 1:0:-1]:
            num = ord(t) - ord("a")
            h += num + 1
            h *= 29
            h %= mod
            cnt[num] -= 1
            if h in d.keys():
                array = d[h]
                for i in range(26):
                    if cnt[i] > 0 and array[i] > 0:ans += 1
        if h not in d.keys(): d[h] = [0]*26
        d[h][ord(s[0]) - ord("a")] += 1
print(ans)