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:
#!/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.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: 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.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 = set()
    for i, ch in enumerate(s):
        initial.add(ch - orda)
        for key in initial:
            rh = RH.get(0, word_len-i-1)
            words[rh][key] += 1
print(ans)

Submission status: Time Limit Exceeded

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

MOD = (1 << 61) - 1
mod_pow = [1] * (10**6 + 10)
base = 1009

for i in range(10**6 + 1):
    mod_pow[i+1] = mod_pow[i] * base % MOD

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

class RollingHash2():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1007
        self.mod1 = 10**9 + 7
        self.mod2 = 10**9 + 9
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2

    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
class SparseTable():
    def __init__(self,A):
        N=len(A)
        n=N.bit_length()
        self.table=[[-1 for i in range(n)] for i in range(N)]

        for i in range(N):
            self.table[i][0]=A[i]

        for j in range(1,n):
            for i in range(0,N-2**j+1):
                f=self.table[i][j-1]
                s=self.table[i+2**(j-1)][j-1]
                self.table[i][j]=min(f,s)

    def query(self,s,t):
        b=t-s+1
        m=b.bit_length()-1
        return min(self.table[s][m],self.table[t-2**m+1][m])

class BIT():
    def __init__(self,n):
        self.BIT=[0]*(n+1)
        self.num=n

    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        while idx <= self.num:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
dic={i:e for e,i in enumerate(alphabetlist)}


import sys

input=sys.stdin.readline

N=int(input())
S=[input().rstrip() for i in range(N)]
for i in range(N):
    temp=[S[i][-j-1] for j in range(len(S[i]))]
    S[i]="".join(temp)
S.sort()

exact=[0 for i in range(N)]
for i in range(1,N):
    id=0
    limit=min(len(S[i]),len(S[i-1]))
    while limit>id and S[i][id]==S[i-1][id]:
        id+=1
    exact[i]=id

lastappear=[[-1 for i in range(26)] for j in range(N)]
for i in range(N):
    for j in range(len(S[i])):
        id=dic[S[i][j]]
        lastappear[i][id]=j

def Solve():
    global S,exact,lastappear
    Sparse=SparseTable(exact)

    def cond(s,n,val):
        if n==N:
            return False
        check=Sparse.query(s,n)
        return check>=val

    def solve(alpha):
        query=[]
        for i in range(N):
            if S[i][-1]==alpha and i!=N-1 and exact[i+1]>=len(S[i])-1:
                start=i+1
                end=N
                while end-start>1:
                    test=(end+start)//2
                    if cond(i+1,test,len(S[i])-1):
                        start=test
                    else:
                        end=test
                query.append((len(S[i])-1,i+1,start+1))
            id=lastappear[i][dic[alpha]]
            if id!=-1:
                query.append((id,N+1,i+1))
        query.sort(reverse=True)
        res=0
        bit=BIT(N)
        for val,l,r in query:
            if l==N+1:
                bit.update(r,1)
            else:
                res+=bit.query(r)-bit.query(l)
        return res


    ans=0
    for alpha in alphabetlist:
        ans+=solve(alpha)
    return ans

ans=0
ans+=Solve()
S=S[::-1]
exact=[0]+exact[N-1:0:-1]
lastappear=lastappear[::-1]
ans+=Solve()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SparseTable():
    def __init__(self,A):
        N=len(A)
        n=N.bit_length()
        self.table=[[-1 for i in range(n)] for i in range(N)]

        for i in range(N):
            self.table[i][0]=A[i]

        for j in range(1,n):
            for i in range(0,N-2**j+1):
                f=self.table[i][j-1]
                s=self.table[i+2**(j-1)][j-1]
                self.table[i][j]=min(f,s)

    def query(self,s,t):
        b=t-s+1
        m=b.bit_length()-1
        return min(self.table[s][m],self.table[t-2**m+1][m])

class BIT():
    def __init__(self,n):
        self.BIT=[0]*(n+1)
        self.num=n

    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        while idx <= self.num:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
dic={i:e for e,i in enumerate(alphabetlist)}


import sys

input=sys.stdin.readline

N=int(input())
S=[input().rstrip() for i in range(N)]
for i in range(N):
    temp=[S[i][-j-1] for j in range(len(S[i]))]
    S[i]="".join(temp)
S.sort()

exact=[0 for i in range(N)]
for i in range(1,N):
    id=0
    limit=min(len(S[i]),len(S[i-1]))
    while limit>id and S[i][id]==S[i-1][id]:
        id+=1
    exact[i]=id

lastappear=[[-1 for i in range(26)] for j in range(N)]
for i in range(N):
    for j in range(len(S[i])):
        id=dic[S[i][j]]
        lastappear[i][id]=j

def Solve():
    global S,exact,lastappear
    Sparse=SparseTable(exact)

    def cond(s,n,val):
        if n==N:
            return False
        check=Sparse.query(s,n)
        return check>=val

    query=[]
    bit=[BIT(N) for i in range(26)]
    for i in range(N):
        if i!=N-1 and exact[i+1]>=len(S[i])-1:
            start=i+1
            end=N
            while end-start>1:
                test=(end+start)//2
                if cond(i+1,test,len(S[i])-1):
                    start=test
                else:
                    end=test
            query.append((len(S[i])-1,i+1,start+1,dic[S[i][-1]]))
        for j in range(26):
            if lastappear[i][j]!=-1:
                query.append((lastappear[i][j],N+1,i+1,j))
    query.sort(reverse=True)
    res=0
    for val,l,r,id in query:
        if l==N+1:
            bit[id].update(r,1)
        else:
            res+=bit[id].query(r)-bit[id].query(l)
    return res

ans=0
ans+=Solve()
S=S[::-1]
exact=[0]+exact[N-1:0:-1]
lastappear=lastappear[::-1]
ans+=Solve()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SparseTable():
    def __init__(self,A):
        N=len(A)
        n=N.bit_length()
        self.table=[[-1 for i in range(n)] for i in range(N)]

        for i in range(N):
            self.table[i][0]=A[i]

        for j in range(1,n):
            for i in range(0,N-2**j+1):
                f=self.table[i][j-1]
                s=self.table[i+2**(j-1)][j-1]
                self.table[i][j]=min(f,s)

    def query(self,s,t):
        b=t-s+1
        m=b.bit_length()-1
        return min(self.table[s][m],self.table[t-2**m+1][m])

class BIT():
    def __init__(self,n):
        self.BIT=[0]*(n+1)
        self.num=n

    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        while idx <= self.num:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
dic={i:e for e,i in enumerate(alphabetlist)}


import sys

input=sys.stdin.readline

N=int(input())
S=[input().rstrip() for i in range(N)]
for i in range(N):
    temp=[S[i][-j-1] for j in range(len(S[i]))]
    S[i]="".join(temp)
S.sort()

def Solve(S):
    exact=[0 for i in range(N)]
    for i in range(1,N):
        id=0
        limit=min(len(S[i]),len(S[i-1]))
        while limit>id and S[i][id]==S[i-1][id]:
            id+=1
        exact[i]=id

    lastappear=[[-1 for i in range(26)] for j in range(N)]
    for i in range(N):
        for j in range(len(S[i])):
            id=dic[S[i][j]]
            lastappear[i][id]=j

    Sparse=SparseTable(exact)

    def cond(s,n,val):
        if n==N:
            return False
        check=Sparse.query(s,n)
        return check>=val

    query=[]
    bit=[BIT(N) for i in range(26)]
    for i in range(N):
        if i!=N-1 and exact[i+1]>=len(S[i])-1:
            start=i+1
            end=N
            while end-start>1:
                test=(end+start)//2
                if cond(i+1,test,len(S[i])-1):
                    start=test
                else:
                    end=test
            query.append((len(S[i])-1,i+1,start+1,dic[S[i][-1]]))
        for j in range(26):
            if lastappear[i][j]!=-1:
                query.append((lastappear[i][j],N+1,i+1,j))
    query.sort(reverse=True)
    res=0
    for val,l,r,id in query:
        if l==N+1:
            bit[id].update(r,1)
        else:
            res+=bit[id].query(r)-bit[id].query(l)
    return res

ans=0
ans+=Solve(S)
S=S[::-1]
ans+=Solve(S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SparseTable():
    def __init__(self,A):
        N=len(A)
        n=N.bit_length()
        self.table=[[-1 for i in range(n)] for i in range(N)]

        for i in range(N):
            self.table[i][0]=A[i]

        for j in range(1,n):
            for i in range(0,N-2**j+1):
                f=self.table[i][j-1]
                s=self.table[i+2**(j-1)][j-1]
                self.table[i][j]=min(f,s)

    def query(self,s,t):
        b=t-s+1
        m=b.bit_length()-1
        return min(self.table[s][m],self.table[t-2**m+1][m])

class BIT():
    def __init__(self,n):
        self.BIT=[0]*(n+1)
        self.num=n

    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        while idx <= self.num:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
dic={i:e for e,i in enumerate(alphabetlist)}


import sys

input=sys.stdin.readline

N=int(input())
S=[input().rstrip() for i in range(N)]
for i in range(N):
    temp=[S[i][-j-1] for j in range(len(S[i]))]
    S[i]="".join(temp)
S.sort()

def Solve(S):
    exact=[0 for i in range(N)]
    for i in range(1,N):
        id=0
        limit=min(len(S[i]),len(S[i-1]))
        while limit>id and S[i][id]==S[i-1][id]:
            id+=1
        exact[i]=id

    lastappear=[[-1 for i in range(26)] for j in range(N)]
    for i in range(N):
        for j in range(len(S[i])):
            id=dic[S[i][j]]
            lastappear[i][id]=j

    Sparse=SparseTable(exact)

    def cond(s,n,val):
        if n==N:
            return False
        check=Sparse.query(s,n)
        return check>=val

    def solve(alpha):
        query=[]
        for i in range(N):
            if S[i][-1]==alpha and i!=N-1 and exact[i+1]>=len(S[i])-1:
                start=i+1
                end=N
                while end-start>1:
                    test=(end+start)//2
                    if cond(i+1,test,len(S[i])-1):
                        start=test
                    else:
                        end=test
                query.append((len(S[i])-1,i+1,start+1))
            id=lastappear[i][dic[alpha]]
            if id!=-1:
                query.append((id,N+1,i+1))
        query.sort(reverse=True)
        res=0
        bit=BIT(N)
        for val,l,r in query:
            if l==N+1:
                bit.update(r,1)
            else:
                res+=bit.query(r)-bit.query(l)
        return res


    ans=0
    for alpha in alphabetlist:
        ans+=solve(alpha)
    return ans

ans=0
ans+=Solve(S)
S=S[::-1]
ans+=Solve(S)
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文字目までの種類
check=[[set() for j in range(len(ss[i]))]for i in range(n)]
for i in range(n):
    check[i][0].add(ss[i][0])
    for j in range(1,len(ss[i])):
        check[i][j]=check[i][j-1]|{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 cha(k) in check[i][j-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文字目までの種類
check=[[set() for j in range(len(ss[i]))]for i in range(n)]
for i in range(n):
    check[i][0].add(ss[i][0])
    for j in range(1,len(ss[i])):
        check[i][j]=check[i][j-1]|{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] and (cha(k) in check[i][j-1]):
                    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():
    N = int(input())
    ans = 0
    Ss = []
    orda = ord('a')
    for _ in range(N):
        S = input()[::-1]
        Ss.append(list(map(lambda c:ord(c)-orda, 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 sys

sys.setrecursionlimit(10**7)

N = int(input())
S = []
a = ord('a')
for _ in range(N):
  S.append([ord(c) - a for c in input()][::-1])

_end = -1  #'_'
_count = -2 #'#'
def get_count(root):
  if _count in root:
    return root[_count]
  else:
    c = [0] * 26 + [1 if _end in root else 0]
    for k, n in root.items():
      if k not in (_end, _count):
        cc = get_count(n)
        #print(k, cc)
        for i, v in enumerate(cc):
          if i == k:
            c[k] += cc[-1]
          else:
            c[i] += v
    root[_count] = c
    return c
    
def make_trie(words):
  root = dict()
  for word in words:
    current_dict = root
    for letter in word:
      #letter = ord(letter)
      current_dict = current_dict.setdefault(letter, {})
    current_dict[_end] = _end
 
  return root

def get_subtree(trie, word):
  current_dict = trie
  for letter in word:
    #letter = ord(letter)
    if letter not in current_dict:
      return {}
    current_dict = current_dict[letter]
  return current_dict
  
def in_trie(trie, word):
  return _end in get_subtree(trie, word)

trie = make_trie(S)
#print(trie)
#print(get_subtree(trie, 'cy'))
#print(in_trie(trie, 'cy'))
#print(in_trie(trie, 'cyx'))

ans = 0
for s in S:
  count = get_count(get_subtree(trie, s[:-1]))
  #print(s, '#', count[s[-1]], count)
  ans += count[s[-1]]

print((ans - N))

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self):
        self.child = [None] * 26
        self.counts = [0] * 26

    # def add(self, s, bucket, idx_s):
    #     c = s[idx_s]
    #     if self.child[c] is None:
    #         self.child[c] = Node()
    #     for i, cnt in enumerate(bucket):
    #         if cnt:
    #             self.counts[i] += 1
    #     bucket[c] -= 1
    #     if idx_s >= 1:
    #         self.child[c].add(s, bucket, idx_s - 1)
    #     else:
    #         Leaves.append(self.counts)

    def add(self, s, bucket):
        node = self
        for idx_s, c in zip(range(len(s)-1, -1, -1), s[::-1]):
            if node.child[c] is None:
                node.child[c] = Node()
            for i, cnt in enumerate(bucket):
                if cnt:
                    node.counts[i] += 1
            bucket[c] -= 1
            if idx_s > 0:
                node = node.child[c]
        Leaves.append(node.counts)

    # def get(self, s, idx_s):
    #     c = s[idx_s]
    #     if idx_s > 0:
    #         return self.child[c].get(s, idx_s-1)
    #     else:
    #         return self.counts[c]

Leaves = []
trie = Node()
N = int(input())
S = [[ord(c)-97 for c in input()] for _ in range(N)]
for s in S:
    b = [0] * 26
    for c in s:
        b[c] += 1
    trie.add(s, b)
ans = -N
# for s in S:
#     ans += trie.get(s, len(s)-1)
for s, l in zip(S, Leaves):
    ans += l[s[0]]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict as dd

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

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict as dd
N = int(input())

ans = 0
Ss = []
orda = ord('a')
for _ in range(N):
    S = input()
    Ss.append((len(S), list(map(lambda c:ord(c)-orda, S))))
Ss.sort()

ctkey = 26
RTrie = [0]*27
for i in range(N):
    _, S = Ss.pop()
    charct = Counter(S)
    node = RTrie
    L = len(S)
    for i in range(L-1, -1, -1):
        c = S[i]
        for a in charct.keys():
            if not node[a]:
                node[a] = [0]*27
            node[a][ctkey] += 1
        charct[c] -= 1
        if charct[c] == 0:
            charct.pop(c)
        node = node[c]
    ans += node[ctkey]-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文字目までの種類
check=[[set() for j in range(len(ss[i]))]for i in range(n)]
for i in range(n):
    check[i][0].add(ss[i][0])
    for j in range(1,len(ss[i])):
        check[i][j]=check[i][j-1]|{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
#print(m)
#print(check)
for i in range(n):
    s=""
    l=len(ss[i])
    for j in range(l,0,-1):
        if j!=l:
            s=ss[i][j]+s
        for k in range(26):
            if s in m:
                if m[s][k] and (cha(k) in check[i][j-1]):
                    if cha(k)+s!=ss[i]:
                        ans+=1
                        #print(i,j,k,cha(k))
print(ans)