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: Wrong Answer

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


def main():
    import sys
    from collections import defaultdict
    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 = defaultdict(list)
        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
                    dic[H1[i] << 40 + H2[i]].append(i)
            i -= 1
        for s, h1, h2 in key:
            last = ord(s[-1]) - 97
            h = h1 << 40 + h2
            if L == 1:
                for i in range(len(cnt)):
                    if cnt[i][last] > 0:
                        ans += 1
            else:
                for i in range(len(cnt)):
                    if h in dic:
                        if cnt[i][last] > 0:
                            ans += 1
        #print(L, S, ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

_end = -1  #'_'
_count = -2 #'#'
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, {})
      count = current_dict.get(_count, 0) + 1
      current_dict[_count] = count
    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:
  sub_trees = []
  current = trie
  for i in range(len(s)):
    for c in range(ord('a'), ord('z')+1):#'abcdefghijklmnopqrstuvwxyz':
      if c == s[i]:
        continue
      sub_tree = get_subtree(current, [c])
      ans += get_subtree(sub_tree, s[i:]).get(_count, 0)
      #print(s, i, c, get_subtree(sub_tree, s[i:]), sub_tree)
    current = get_subtree(current, s[i:i+1])
  #print(s, '#', current.get(_count,0), current)
  ans += current.get(_count, 0)

print((ans - N))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
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')
#solve
def solve():
    n = II()
    s = [None] * n
    dp = [None] * n
    for i in range(n):
        dp[i] = [-1] * 26
        s[i] = [input().rstrip(), 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
#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
data = [input() for _ in range(n)]

def f(x,y):
    x = x[::-1]
    y = y[::-1]
    buf = 0
    i=0
    while i < len(y):
        if x[i+buf] != y[i]:
            buf+=1
            if buf>1:
                return 0
        else:
            i+=1
    return 1

cnt = 0
for a,b in list(itertools.combinations(data, 2)):
    if len(a) > len(b):
        cnt += f(a,b)
    elif len(a) < len(b):
        cnt += f(b,a)
print(cnt)

Submission status: Wrong Answer

Solution code:
#

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())
sss = [input() for _ in range(n)]
d = {s[1:]: 0 for s in sss}

for s in sss:
    cnt = Counter(s)
    flag = 0
    for c in cnt:
        k = ord(c) - 97
        flag |= 1 << (k * 15)
    if '' in d:
        d[''] += flag
    for i in range(len(s) - 1, 0, -1):
        c = s[i]
        cnt[c] -= 1
        if cnt[c] == 0:
            flag ^= 1 << ((ord(c) - 97) * 15)
        if s[i:] in d:
            d[s[i:]] += flag

ans = 0
mask = (1 << 15) - 1
for s in sss:
    flag = d[s[1:]]
    bs = ((ord(s[0]) - 97) * 15)
    cnt = (flag >> bs) & mask
    ans += cnt - 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=[input() for _ in range(n)]
ans=0
for i in range(n):
     for j in  range(i+1,n):
          
          if len(a[i])<len(a[j]):
              x=a[i]
              y=a[j]
          elif len(a[i])>len(a[j]):
              x=a[j]
              y=a[i]
          else:
             if a[i]==a[j]:
                ans+=1
             continue 
      
          if len(x)==1 and x in y:
              ans+=1
              #continue  
          else:
          	  if x[0] in y and y[1-len(x):]==x[1:]: 
                    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
data = []
count = 1
for i in range(n):
    data.append(input())
print(data)
for i in range(n):
    for j in range(n):
        if (i < j):
            if (len(data[i]) <= len(data[j])):
               data_s = data[i]
               data_l = data[j]
            if (len(data[i]) > len(data[j])):
                data_s = data[j]
                data_l = data[i]
            while(len(data_l)>len(data_s)):
                data_l = data_l[2:]
                if(len(data_l)==len(data_s)):
                    count+=1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter


class TrieNode:
    def __init__(self):
        self.edges = {}
        self.letter___count = Counter()

    def count_strings(self, word):
        curr_node = self
        for letter in word[:-1]:
            if letter not in curr_node.edges:
                return 0
            curr_node = curr_node.edges[letter]
        return curr_node.letter___count[word[-1]]

    def add(self, word):
        curr_node = self
        counts = Counter(word)
        for letter in word:
            for l in counts:
                curr_node.letter___count[l] += counts[l]
            counts[letter] -= 1
            if letter not in curr_node.edges:
                curr_node.edges[letter] = TrieNode()
            curr_node = curr_node.edges[letter]


def main():
    n = int(input())
    strings = sorted([input()[::-1] for _ in range(n)], key=lambda x: -len(x))
    ans = 0
    trie = TrieNode()
    for word in strings:
        ans += trie.count_strings(word)
        trie.add(word)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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**9+7)
    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)

Submission status: Wrong Answer

Solution code:
import re

n = int(input())
count = 0
strings = []

for _ in range(n):
    str = input()
    for existing_str in strings:
        
        # existing_str => strが可能か
        if len(str) == 1:
            regex = "^.*{}.*$".format(str)
        else:
            regex = '^.*' + '.?'.join(str) + '$'
#         print(regex)
        if re.compile(regex).match(existing_str):
            count += 1
#             print(str, existing_str)
            continue
            
        # string => existing_strが可能か
        if len(existing_str) == 1:
            regex = "^.*{}.*$".format(existing_str)
        else:
            regex = '^.*' + '.?'.join(existing_str) + '$'
        if re.compile(regex).match(str):
            count += 1
#             print(str, existing_str)
            continue

    strings.append(str)
    
print(count)

Submission status: Wrong Answer

Solution code:
import collections as c
n = int(input())
s = []
for i in range(n):
    s.append(input())
s.sort(key = lambda x:len(x))
ans = 0

for i in range(1,n):
    x = c.Counter(s[i])
    for t in range(i-1):
        y = c.Counter(s[t])
        for a,b in y.items():
            if x[a]<b:
                break
        else:
            ans += 1
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=input()
a=[]
for i in range(n):
    x=raw_input()
    a.append([len(x),x[::-1]])
a.sort()
d={}
c=0
for i in range(n):
    brr=[0 for j in range(26)]
    x=a[i][1]
    y=x[:len(x)-1]
    e=""
    d1={}
    for i in x:
        d1[i]=d1.get(i,0)+1
    for i in range(len(x)):
        arr=d.get(e,brr)
        for j in range(26):
            if(d1.get(chr(97+j),0)>0):
                c+=arr[j]
        d1[x[i]]-=1
        e+=x[i]
    d[y]=d.get(y,brr)
    d[y][ord(x[-1])-97]+=1
print c

Submission status: Time Limit Exceeded

Solution code:
n=input()
a=[]
for i in range(n):
    x=raw_input()
    a.append([len(x),x])
a.sort()
d={}
c=0
for i in range(n):
    brr=[0 for j in range(26)]
    x=a[i][1]
    if len(x)==1:
        y=""
    else:
        y=x[1:]
    y=y[::-1]
    e=""
    d1={}
    for i in x:
        d1[i]=d1.get(i,0)+1
    for i in range(len(x)-1,-1,-1):
        arr=d.get(e,brr)
        for j in range(26):
            if(d1.get(chr(97+j),0)>0):
                c+=arr[j]
        d1[x[i]]-=1
        e+=x[i]
    d[y]=d.get(y,brr)
    d[y][ord(x[0])-97]+=1
print c

Submission status: Time Limit Exceeded

Solution code:
class Trie:
    class Node:
        def __init__(self,c):
            self.c=c
            self.next_c_id={}
            #self.common=0
            self.end=-1

    def __init__(self):
        self.trie=[self.Node('')]
    
    def add(self,id,s):
        i=0
        now=0
        ary=[0]
        while i<len(s) and s[i] in self.trie[now].next_c_id:
            now=self.trie[now].next_c_id[s[i]]
            ary.append(now)
            #self.trie[now].common+=1
            i+=1
        while i<len(s):
            self.trie[now].next_c_id[s[i]]=len(self.trie)
            now=len(self.trie)
            ary.append(now)
            self.trie.append(self.Node(s[i]))
            #self.trie[now].common+=1
            i+=1
        self.trie[now].end=id
        return ary

def main(s):
    tr=Trie()
    s.sort(key=lambda x:len(x))
    ans=0
    for i,x in enumerate(s):
        ary=tr.add(i,x)
        seen=set(())
        while ary:
            id=ary.pop()
            for nv in seen&tr.trie[id].next_c_id.keys():
                if tr.trie[tr.trie[id].next_c_id[nv]].end>=0 and tr.trie[tr.trie[id].next_c_id[nv]].end!=i:
                    ans+=1
            seen.add(tr.trie[id].c)
    print(ans)

if __name__=='__main__':
    a2n=lambda x:ord(x)-ord('a')
    n=int(input())
    s=[list(map(a2n,list(input()))) for _ in range(n)]
    [x.reverse() for x in s]
    main(s)

Submission status: Time Limit Exceeded

Solution code:
class Trie:
    class Node:
        def __init__(self,c):
            self.c=c
            self.next_c_id={}
            #self.common=0
            self.end=-1

    def __init__(self):
        self.trie=[self.Node('')]
    
    def add(self,id,s):
        i=0
        now=0
        ary=[0]
        while i<len(s) and s[i] in self.trie[now].next_c_id:
            now=self.trie[now].next_c_id[s[i]]
            ary.append(now)
            #self.trie[now].common+=1
            i+=1
        while i<len(s):
            self.trie[now].next_c_id[s[i]]=len(self.trie)
            now=len(self.trie)
            ary.append(now)
            self.trie.append(self.Node(s[i]))
            #self.trie[now].common+=1
            i+=1
        self.trie[now].end=id
        return ary
    
    def search(self,s):
        i=0
        now=0
        ary=[0]
        while i<len(s) and s[i] in self.trie[now].next_c_id:
            now=self.trie[now].next_c_id[s[i]]
            ary.append(now)
            i+=1
        if i<len(s):return []
        return ary

def main(s):
    tr=Trie()
    s.sort(key=lambda x:len(x))
    #for id,x in enumerate(s):
    #    tr.add(id,x)
    ans=0
    for i,x in enumerate(s):
        ary=tr.add(i,x)
        #ary=tr.search(x)
        seen=set(())
        #print(x,ary)
        while ary:
            id=ary.pop()
            for nv in seen.intersection(tr.trie[id].next_c_id.keys()):
                if tr.trie[tr.trie[id].next_c_id[nv]].end>=0 and tr.trie[tr.trie[id].next_c_id[nv]].end!=i:
                    ans+=1
            seen.add(tr.trie[id].c)
        #print(x,ans)
    print(ans)

if __name__=='__main__':
    n=int(input())
    s=[list(input()) for _ in range(n)]
    [x.reverse() for x in s]
    main(s)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=[list(input()) for _ in range(n)]
[x.reverse() for x in s]

class Trie:
    class Node:
        def __init__(self,c):
            self.c=c
            self.next_c_id={}
            self.common=0
            self.end=-1

    def __init__(self):
        self.trie=[self.Node('')]
    
    def add(self,id,s):
        i=0
        now=0
        while i<len(s) and s[i] in self.trie[now].next_c_id:
            now=self.trie[now].next_c_id[s[i]]
            self.trie[now].common+=1
            i+=1
        while i<len(s):
            self.trie[now].next_c_id[s[i]]=len(self.trie)
            now=len(self.trie)
            self.trie.append(self.Node(s[i]))
            self.trie[now].common+=1
            i+=1
        self.trie[now].end=id
    
    def search(self,s):
        i=0
        now=0
        ary=[0]
        while i<len(s) and s[i] in self.trie[now].next_c_id:
            now=self.trie[now].next_c_id[s[i]]
            ary.append(now)
            i+=1
        if i<len(s):return []
        return ary

tr=Trie()
#s.sort(key=lambda x:len(x))
for id,x in enumerate(s):
    tr.add(id,x)
ans=0
for i,x in enumerate(s):
    ary=tr.search(x)
    seen=set(())
    #print(x,ary)
    while ary:
        id=ary.pop()
        for nv in seen.intersection(tr.trie[id].next_c_id.keys()):
            if tr.trie[tr.trie[id].next_c_id[nv]].end>=0 and tr.trie[tr.trie[id].next_c_id[nv]].end!=i:
                ans+=1
        seen.add(tr.trie[id].c)
    #print(x,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
T = [input()[::-1].strip() for i in range(N)]

#N = 10000
#import random
#import string
#T = [''.join(random.choices(string.ascii_lowercase, k=random.randint(1,20))) for i in range(N)]

class TrieTree:
    class Node:
        def __init__(self):
            self.ch = defaultdict(TrieTree.Node)
            self.cnt = 0
            self.end = False

    def __init__(self):
        self.root = self.Node()

    def register(self,word):
        node = self.root
        for w in word:
            node.cnt += 1
            node = node.ch[w]
        node.cnt += 1
        node.end = True
    
    def prefix(self, word):
        node = self.root
        for w in word:
            if w not in node.ch:
                return False
            else:
                node = node.ch[w]
        return node

tt = TrieTree()
T.sort(key=len, reverse=True)
ans = 0
for word in T:
    tt.register(word)
    pre = word[:-1]
    last = word[-1]
    node = tt.prefix(pre)
    if not node:
        continue
    df = [node]
    while df:
        node = df.pop()
        for c, nnode in node.ch.items():
            if c == last:
                ans += node.ch[last].cnt
            else:
                df.append(nnode)
    ans -= 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
T = [input()[::-1].strip() for i in range(N)]

class TrieTree:
    class Node:
        def __init__(self):
            self.ch = defaultdict(TrieTree.Node)
            self.cnt = 0
            self.end = False

    def __init__(self):
        self.root = self.Node()

    def register(self,word):
        node = self.root
        for w in word:
            node.cnt += 1
            node = node.ch[w]
        node.cnt += 1
        node.end = True
    
    def prefix(self, word):
        node = self.root
        for w in word:
            if w not in node.ch:
                return False
            else:
                node = node.ch[w]
        return node

tt = TrieTree()
for word in T:
    tt.register(word)

ans = 0
for word in T:
    pre = word[:-1]
    last = word[-1]
    node = tt.prefix(pre)
    if not node:
        continue
    df = [node]
    while df:
        node = df.pop()
        for c, nnode in node.ch.items():
            if c == last:
                ans += node.ch[last].cnt
            else:
                df.append(nnode)
    ans -= 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
T = [input()[::-1].strip() for i in range(N)]
R,S = zip(*[(t[:-1],t[-1]) for t in T])


tt = defaultdict(lambda : defaultdict(int))

for word in T:
    w = ""
    t = word
    for s in word:
        for u in set(t):
            tt[w][u] += 1
        t = t[1:]
        w += s

ans = 0
for word in T:
    if len(word) > 1:
        w,t = word[:-1],word[-1]
    else:
        w,t = "",word
    ans += tt[w][t] - 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 61 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.defaultdict(int)
    ans = 0
    S = [SI() for _ in range(N)]
    for s in S:
        cnt[s[1:]] |= 1<<(ord(s[0])-ord('a'))

    for s in S:
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        for i in range(len(s),1,-1):
            if i == len(s):
                d = ''
            else:
                d = s[i:]
            ans += bin(cnt[d] & a[i-1]).count('1')

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 61 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.Counter()
    ans = 0
    C = []
    for _ in range(N):
        s = SI()
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        for i in range(len(s),-1,-1):
            if i == len(s):
                c = 0
            else:
                c = (c * 27 + ord(s[i]) - ord('a') + 1) % MOD
            if i > 0:
                d = c * 27
                b = 1
                for j in range(26):
                    if a[i-1] & b:
                        cnt[(d+j+1)%MOD] += 1
                    b <<= 1
        C.append(c)
    for c in C:
        ans += cnt[c] - 1

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 61 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.Counter()
    ans = 0
    S = [SI() for _ in range(N)]
    C = []
    for s in S:
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        for i in range(len(s),-1,-1):
            if i == len(s):
                c = 0
            else:
                c = (c * 27 + ord(s[i]) - ord('a') + 1) % MOD
            if i > 0:
                d = c * 27
                for j in range(26):
                    if a[i-1] & (1<<j):
                        cnt[(d+j+1)%MOD] += 1
        C.append(c)
    for c in C:
        ans += cnt[c] - 1

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 61 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.Counter()
    ans = 0
    S = [SI() for _ in range(N)]
    for s in S:
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        for i in range(len(s),-1,-1):
            if i == len(s):
                c = 0
            else:
                c = (c * 27 + ord(s[i]) - ord('a') + 1) % MOD
            if i > 0:
                d = (c * 27) % MOD
                for j in range(26):
                    if a[i-1] & (1<<j):
                        cnt[(d+j+1)%MOD] += 1
    for s in S:
        c = 0
        for i in range(len(s)-1,-1,-1):
            c = (c * 27 + ord(s[i]) - ord('a') + 1) % MOD
        ans += cnt[c] - 1

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N = int(input())
S = [input()[:-1][::-1] for _ in range(N)]
nodes = [[-1]*26+[0]]

for Si in S:
    cnt = [0]*26
    
    for c in Si:
        cnt[ord(c)-ord('a')] += 1
        
    node_id = 0
    
    for c in Si:
        for i in range(26):
            if cnt[i]>0:
                next_id = nodes[node_id][i]
                
                if next_id==-1:
                    next_id = len(nodes)
                    nodes[node_id][i] = next_id
                    nodes.append([-1]*26+[0])
                    
                nodes[next_id][-1] += 1
        
        node_id = nodes[node_id][ord(c)-ord('a')]
        cnt[ord(c)-ord('a')] -= 1
        
ans = 0

for Si in S:
    node_id = 0
    flag = True
    
    for c in Si:
        next_id = nodes[node_id][ord(c)-ord('a')]
        
        if next_id==-1:
            flag = False
            break
    
        node_id = next_id
    
    if flag:
        ans += nodes[node_id][-1]

print(ans-N)

Submission status: Time Limit Exceeded

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

N = int(input())
S = [input()[:-1][::-1] for _ in range(N)]
nodes = [[-1]*26+[0]]

for Si in S:
    cnt = [0]*26
    
    for c in Si:
        cnt[ord(c)-ord('a')] += 1
        
    node_id = 0
    
    for c in Si:
        for alpha in 'abcdefghijklmnopqrstuvwxyz':
            if cnt[ord(alpha)-ord('a')]>0:
                next_id = nodes[node_id][ord(alpha)-ord('a')]
        
                if next_id==-1:
                    next_id = len(nodes)
                    nodes[node_id][ord(alpha)-ord('a')] = next_id
                    nodes.append([-1]*26+[0])
                    
                nodes[next_id][-1] += 1
        
        node_id = nodes[node_id][ord(c)-ord('a')]
        cnt[ord(c)-ord('a')] -= 1
        
ans = 0

for Si in S:
    node_id = 0
    flag = True
    
    for c in Si:
        next_id = nodes[node_id][ord(c)-ord('a')]
        
        if next_id==-1:
            flag = False
            break
    
        node_id = next_id
    
    if flag:
        ans += nodes[node_id][-1]

print(ans-N)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

word = []
for i in range(n):
  input_line = input()
  word.append(input_line)
  #print(word[i])
  
# 一致する可能性のある組み合わせを数える cou1
# 一致する可能性のある組み合わせを格納するリスト case
cou1 = 0
case = []

for i in range(n):
  check1 = word[i]
  for j in range(n):
    if i != j:
      check2 = word[j]
      k = 0
      l = 0
      while k < len(word[i]) and l < len(word[j]):
        if check1[k] == check2[l]:
          k += 1
          l += 1
          if l == len(word[j]):
            case.append([i, j])
            cou1 += 1
            #print(case)
            break
        else:
          k += 1
      l = 0
    else:
      continue

#print(cou1)
      
#正解の組み合わせを数える cou2
cou2 = 0
for i in range(cou1):
  j = case[i][0]
  k = case[i][1]
  #l = len(word[j])
  m = len(word[k])
  if m == 1:
    cou2 += 1
  elif word[j][l - m + 1:] == word[k][1:]:
    cou2 += 1
  else:
    continue

print(cou2)

Submission status: Time Limit Exceeded

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

N = int(input())
S = [input().rstrip()[::-1] for i in range(N)]
S.sort(key=lambda x:-len(x))
P = 2**61 - 1

from collections import defaultdict,Counter
D = defaultdict(lambda: Counter())

ans = 0
for s in S:
    sets = [set()]
    for c in s[::-1]:
        i = ord(c) - ord('a')
        sets.append(sets[-1] | {i})
    sets.reverse()
    nxs = []
    a = 0
    for l,(c,st) in enumerate(zip(s,sets)):
        for j in st:
            na = (a*27 + (j+1)) % P
            nxs.append((na,l))
        i = ord(c) - ord('a') + 1
        a *= 27
        a += i
        a %= P
    if a in D[len(s)-1]:
        ans += D[len(s)-1][a]
    for na,l in nxs:
        D[l][na] += 1

print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
S = [input().rstrip()[::-1] for i in range(N)]
S.sort(key=lambda x:-len(x))
P = 2**61 - 1

from collections import defaultdict,Counter
D = defaultdict(lambda: Counter())

ans = 0
for s in S:
    sets = [0]
    for c in s[::-1]:
        i = ord(c) - ord('a')
        sets.append(sets[-1] | (1<<i))
    sets.reverse()
    nxs = []
    a = 0
    for l,(c,st) in enumerate(zip(s,sets)):
        for j in range(26):
            if st&(1<<j):
                na = (a*27 + (j+1)) % P
                nxs.append((na,l))
        i = ord(c) - ord('a') + 1
        a *= 27
        a += i
        a %= P
    if a in D[len(s)-1]:
        ans += D[len(s)-1][a]
    for na,l in nxs:
        D[l][na] += 1

print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
S = [input().rstrip()[::-1] for i in range(N)]
S.sort(key=lambda x:-len(x))
P = 2**61 - 1

from collections import defaultdict,Counter
D = defaultdict(lambda: Counter())

ans = 0
for s in S:
    a = 0
    for c in s:
        i = ord(c) - ord('a') + 1
        a *= 27
        a += i
        a %= P
    if a in D[len(s)-1]:
        ans += D[len(s)-1][a]
    sets = [0]
    for c in s[::-1]:
        i = ord(c) - ord('a')
        sets.append(sets[-1] | (1<<i))
    sets.reverse()
    a = 0
    for l,(c,st) in enumerate(zip(s,sets)):
        for j in range(26):
            if st&(1<<j):
                na = (a*27 + (j+1)) % P
                D[l][na] += 1
        i = ord(c) - ord('a') + 1
        a *= 27
        a += i
        a %= P

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 = defaultdict(set)
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
        if suffix_hash in wanted:
            for alpha in wanted[suffix_hash]:
                if alpha in alpha_set:
                    ans += 1

    suffix_of_S = (hash_of_S[len(S)] - hash_of_S[1] * pow(root, (len(S) - 1), MOD)) % MOD
    wanted[suffix_of_S].add(S[0])

print(ans)