You Are Given Some Strings... (Codeforces 1202E)
Tags: Others, string suffix structures

You are given a string $$$t$$$ and $$$n$$$ strings $$$s_1, s_2, \dots, s_n$$$. All strings consist of lowercase Latin letters.Let $$$f(t, s)$$$ be the number of occurences of string $$$s$$$ in string $$$t$$$. For example, $$$f('\text{aaabacaa}', '\text{aa}') = 3$$$, and $$$f('\text{ababa}', '\text{aba}') = 2$$$.Calculate the value of $$$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j)$$$, where $$$s + t$$$ is the concatenation of strings $$$s$$$ and $$$t$$$. Note that if there are two pairs $$$i_1$$$, $$$j_1$$$ and $$$i_2$$$, $$$j_2$$$ such that $$$s_{i_1} + s_{j_1} = s_{i_2} + s_{j_2}$$$, you should include both $$$f(t, s_{i_1} + s_{j_1})$$$ and $$$f(t, s_{i_2} + s_{j_2})$$$ in answer.

Input: The first line contains string $$$t$$$ ($$$1 \le |t| \le 2 \cdot 10^5$$$).The second line contains integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).Each of next $$$n$$$ lines contains string $$$s_i$$$ ($$$1 \le |s_i| \le 2 \cdot 10^5$$$).It is guaranteed that $$$\sum\limits_{i=1}^{n} |s_i| \le 2 \cdot 10^5$$$. All strings consist of lowercase English letters.

Output: Print one integer — the value of $$$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j)$$$.


Sample Inputs:
aaabacaa
2
a
aa

aaabacaa
4
a
a
a
b

Sample Outputs:
5

33

Solution (Python):
from collections import deque, defaultdict
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def insert(s, G):
    j = 0
    for i in s:
        if not G[j][i] ^ -1:
            G[j][i] = len(G)
            G.append([-1] * 26)
            j = len(G) - 1
        else:
            j = G[j][i]
    return j

def aho_corasick(s):
    G = [[-1] * 26]
    d = defaultdict(lambda : 0)
    for s0 in s:
        x = insert(s0, G)
        d[x] += 1
    G0 = G[0]
    for i in range(26):
        G0[i] = max(G0[i], 0)
    l = len(G)
    c = [0] * l
    for i in d:
        c[i] += d[i]
    f = [0] * l
    q = deque()
    q.append(0)
    dist = [-1] * l
    dist[0] = 0
    cnt = [0] * l
    p = []
    while q:
        i = q.popleft()
        p.append(i)
        di = dist[i]
        Gi = G[i]
        for j in range(26):
            k = Gi[j]
            if k <= 0:
                continue
            q.append(k)
            dist[k] = di + 1
            if not di:
                continue
            u = i
            while True:
                u = f[u]
                if G[u][j] ^ -1:
                    f[k] = G[u][j]
                    break
    cnt = list(c)
    for i in p:
        cnt[i] += cnt[f[i]]
    return (G, cnt, f, c)

def search(s, G, cnt, f, c):
    l = len(s)
    ans = [0] * l
    j = 0
    for i in range(l):
        si = s[i]
        if G[j][si] ^ -1:
            j = G[j][si]
        else:
            while True:
                j = f[j]
                if G[j][si] ^ -1:
                    j = G[j][si]
                    break
                elif not j:
                    j = G[j][si]
                    break
        ans[i] = c[j] + cnt[f[j]]
    return ans
t = list(input().rstrip())
for i in range(len(t)):
    t[i] -= 97
n = int(input())
s = []
for _ in range(n):
    s0 = list(input().rstrip())
    for i in range(len(s0)):
        s0[i] -= 97
    s.append(s0)
(G, cnt, f, c) = aho_corasick(s)
u = search(t, G, cnt, f, c)
for i in range(n):
    s[i].reverse()
t.reverse()
(G, cnt, f, c) = aho_corasick(s)
v = search(t, G, cnt, f, c)
v.reverse()
ans = 0
for (i, j) in zip(u[:-1], v[1:]):
    ans += i * j
print(ans)

Solution (Python):
class Node(object):

    def __init__(self):
        super(Node, self).__init__()
        self.next = [-1] * 26
        self.trans = []
        self.matches = 0
        self.leaf = 0
        self.link = 0

class AhoCorasick(object):

    def __init__(self):
        super(AhoCorasick, self).__init__()
        self.T = [Node()]
        self.T[0].link = 0

    def insert_trie(self, s):
        v = 0
        for i in range(len(s)):
            c = ord(s[i]) - ord('a')
            if self.T[v].next[c] == -1:
                self.T[v].trans.append(c)
                self.T[v].next[c] = len(self.T)
                self.T.append(Node())
            v = self.T[v].next[c]
        self.T[v].leaf += 1
        self.T[v].matches += 1

    def set_suffix_link(self, S):
        Q = []
        for j in range(len(S)):
            Q.append((j, 0, 0, 0))
        i = 0
        while i < len(Q):
            (j, ind, v, suff) = Q[i]
            i += 1
            c = ord(S[j][ind]) - ord('a')
            if ind > 0:
                while suff > 0 and self.T[suff].next[c] == -1:
                    suff = self.T[suff].link
                if self.T[suff].next[c] != -1:
                    suff = self.T[suff].next[c]
            v = self.T[v].next[c]
            self.T[v].link = suff
            if ind + 1 < len(S[j]):
                Q.append((j, ind + 1, v, suff))

    def set_matches(self):
        i = 0
        Q = [0]
        while i < len(Q):
            v = Q[i]
            self.T[v].matches = self.T[v].leaf + self.T[self.T[v].link].matches
            for c in self.T[v].trans:
                Q.append(self.T[v].next[c])
            i += 1

    def build(self, S):
        for i in range(len(S)):
            self.insert_trie(S[i])
        self.set_suffix_link(S)
        self.set_matches()

    def get(self, s):
        v = 0
        matches = []
        for i in range(len(s)):
            c = ord(s[i]) - ord('a')
            while v > 0 and self.T[v].next[c] == -1:
                v = self.T[v].link
            if self.T[v].next[c] != -1:
                v = self.T[v].next[c]
            matches.append(self.T[v].matches)
        return matches

    def printTree(self):
        for i in range(len(self.T)):
            print(str(i) + ' leaf:' + str(self.T[i].leaf) + ' link:' + str(self.T[i].link) + ' matches:' + str(self.T[i].matches) + ' : ', end='')
            for j in range(26):
                print(' ' + str(chr(j + ord('a'))) + '-' + (str(self.T[i].next[j]) if self.T[i].next[j] != -1 else '_') + ' ', end='')
            print()
t = input()
n = int(input())
patterns = []
patterns_rev = []
for i in range(n):
    s = input()
    patterns.append(s)
    patterns_rev.append(s[::-1])
t1 = AhoCorasick()
t2 = AhoCorasick()
t1.build(patterns)
t2.build(patterns_rev)
x1 = t1.get(t)
x2 = t2.get(t[::-1])[::-1]
ans = 0
for i in range(len(x1) - 1):
    ans += x1[i] * x2[i + 1]
print(ans)

Solution (Python):
if 1:
    (standard_input, packages, output_together) = (1, 1, 1)
    (dfs, hashing, read_from_file) = (0, 0, 0)
    de = 1
    if standard_input:
        import io, os, sys
        input = lambda : sys.stdin.readline().strip()
        inf = float('inf')

        def I():
            return input()

        def II():
            return int(input())

        def MII():
            return map(int, input().split())

        def LI():
            return list(input().split())

        def LII():
            return list(map(int, input().split()))

        def LFI():
            return list(map(float, input().split()))

        def GMI():
            return map(lambda x: int(x) - 1, input().split())

        def LGMI():
            return list(map(lambda x: int(x) - 1, input().split()))
    if packages:
        from io import BytesIO, IOBase
        import math
        import random
        import os
        import bisect
        import typing
        from collections import Counter, defaultdict, deque
        from copy import deepcopy
        from functools import cmp_to_key, lru_cache, reduce
        from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
        from itertools import accumulate, combinations, permutations, count, product
        from operator import add, iand, ior, itemgetter, mul, xor
        from string import ascii_lowercase, ascii_uppercase, ascii_letters
        from typing import *
        BUFSIZE = 4096
    if output_together:

        class FastIO(IOBase):
            newlines = 0

            def __init__(self, file):
                self._fd = file.fileno()
                self.buffer = BytesIO()
                self.writable = 'x' in file.mode or 'r' not in file.mode
                self.write = self.buffer.write if self.writable else None

            def read(self):
                while True:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    if not b:
                        break
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines = 0
                return self.buffer.read()

            def readline(self):
                while self.newlines == 0:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    self.newlines = b.count(b'\n') + (not b)
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines -= 1
                return self.buffer.readline()

            def flush(self):
                if self.writable:
                    os.write(self._fd, self.buffer.getvalue())
                    (self.buffer.truncate(0), self.buffer.seek(0))

        class IOWrapper(IOBase):

            def __init__(self, file):
                self.buffer = FastIO(file)
                self.flush = self.buffer.flush
                self.writable = self.buffer.writable
                self.write = lambda s: self.buffer.write(s.encode('ascii'))
                self.read = lambda : self.buffer.read().decode('ascii')
                self.readline = lambda : self.buffer.readline().decode('ascii')
        sys.stdout = IOWrapper(sys.stdout)
    if dfs:
        from types import GeneratorType

        def bootstrap(f, stack=[]):

            def wrappedfunc(*args, **kwargs):
                if stack:
                    return f(*args, **kwargs)
                else:
                    to = f(*args, **kwargs)
                    while True:
                        if type(to) is GeneratorType:
                            stack.append(to)
                            to = next(to)
                        else:
                            stack.pop()
                            if not stack:
                                break
                            to = stack[-1].send(to)
                    return to
            return wrappedfunc
    if hashing:
        RANDOM = random.getrandbits(20)

        class Wrapper(int):

            def __init__(self, x):
                int.__init__(x)

            def __hash__(self):
                return super(Wrapper, self).__hash__() ^ RANDOM
    if read_from_file:
        file = open('input.txt', 'r').readline().strip()[1:-1]
        fin = open(file, 'r')
        input = lambda : fin.readline().strip()
        output_file = open('output.txt', 'w')

        def fprint(*args, **kwargs):
            print(*args, **kwargs, file=output_file)
    if de:

        def debug(*args):
            print('\x1b[92m', end='')
            print(*args)
            print('\x1b[0m', end='')

def sa_naive(s):
    n = len(s)
    return sorted(range(n), key=lambda i: s[i:])

def sa_doubling(s):

    def key(i):
        if i + k < n:
            return (rank[i], rank[i + k])
        return (rank[i], -1)
    smax = max(s) + 1
    n = len(s)
    sa = list(range(n))
    rank = s[:]
    tmp = [0] * n
    k = 1
    while k < n:
        sa.sort(key=key)
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]] + (key(sa[i - 1]) < key(sa[i]))
        (rank, tmp) = (tmp, rank)
        k <<= 1
    return sa

def sa_is(s, upper, THRESHHOLD_NAIVE=20, THRESHHOLD_DOUBLE=100):

    def induce(lms):
        for i in range(n):
            sa[i] = -1
        buf = sum_s[:]
        for d in lms:
            if d == n:
                continue
            sa[buf[s[d]]] = d
            buf[s[d]] += 1
        buf = sum_l[:]
        sa[buf[s[n - 1]]] = n - 1
        buf[s[n - 1]] += 1
        for i in range(n):
            v = sa[i]
            if v >= 1 and (not ls[v - 1]):
                sa[buf[s[v - 1]]] = v - 1
                buf[s[v - 1]] += 1
        buf = sum_l[:]
        for i in range(n)[::-1]:
            v = sa[i]
            if v >= 1 and ls[v - 1]:
                buf[s[v - 1] + 1] -= 1
                sa[buf[s[v - 1] + 1]] = v - 1
    n = len(s)
    if n == 0:
        return []
    if n == 1:
        return [0]
    if n <= THRESHHOLD_NAIVE:
        return sa_naive(s)
    if n <= THRESHHOLD_DOUBLE:
        return sa_doubling(s)
    sa = [0] * n
    ls = [0] * n
    for i in range(n - 1)[::-1]:
        if s[i] == s[i + 1]:
            ls[i] = ls[i + 1]
        else:
            ls[i] = int(s[i] < s[i + 1])
    sum_l = [0] * (upper + 1)
    sum_s = [0] * (upper + 1)
    for (i, x) in enumerate(ls):
        if not x:
            sum_s[s[i]] += 1
        else:
            sum_l[s[i] + 1] += 1
    for i in range(upper + 1):
        sum_s[i] += sum_l[i]
        if i < upper:
            sum_l[i + 1] += sum_s[i]
    lms_map = [-1] * (n + 1)
    lms = []
    m = 0
    for i in range(1, n):
        if not ls[i - 1] and ls[i]:
            lms_map[i] = m
            lms.append(i)
            m += 1
    induce(lms)
    if m:
        sorted_lms = []
        for v in sa:
            if v == -1:
                print('minuse')
            if lms_map[v] != -1:
                sorted_lms.append(v)
        rec_s = [0] * m
        rec_upper = 0
        rec_s[lms_map[sorted_lms[0]]] = 0
        for i in range(1, m):
            l = sorted_lms[i - 1]
            r = sorted_lms[i]
            end_l = lms[lms_map[l] + 1] if lms_map[l] + 1 < m else n
            end_r = lms[lms_map[r] + 1] if lms_map[r] + 1 < m else n
            same = 1
            if end_l - l != end_r - r:
                same = 0
            else:
                while l < end_l:
                    if s[l] != s[r]:
                        break
                    l += 1
                    r += 1
                if l == n or s[l] != s[r]:
                    same = 0
            if not same:
                rec_upper += 1
            rec_s[lms_map[sorted_lms[i]]] = rec_upper
        rec_sa = sa_is(rec_s, rec_upper)
        for i in range(m):
            sorted_lms[i] = lms[rec_sa[i]]
        induce(sorted_lms)
    return sa

def suffix_array(S, compress=True):
    if compress:
        ch = sorted(set(S))
        ctoi = {c: i for (i, c) in enumerate(ch, 1)}
        S = [ctoi[s] for s in S]
    upper = max(S) + 1
    return sa_is(S, upper)

def construct_lcp(s, sa):
    n = len(s)
    assert n >= 1
    rank = [0] * n
    for i in range(n):
        rank[sa[i]] = i
    lcp = [0] * n
    h = 0
    for i in range(n):
        if h > 0:
            h -= 1
        if rank[i] == 0:
            continue
        j = sa[rank[i] - 1]
        while j + h < n and i + h < n:
            if s[j + h] != s[i + h]:
                break
            h += 1
        lcp[rank[i] - 1] = h
    return lcp

class SparseTable:

    def __init__(self, data, merge_method):
        self.note = [0] * (len(data) + 1)
        self.merge_method = merge_method
        (l, r, v) = (1, 2, 0)
        while True:
            for i in range(l, r):
                if i >= len(self.note):
                    break
                self.note[i] = v
            else:
                l *= 2
                r *= 2
                v += 1
                continue
            break
        self.ST = [[0] * len(data) for _ in range(self.note[-1] + 1)]
        self.ST[0] = data
        for i in range(1, len(self.ST)):
            for j in range(len(data) - (1 << i) + 1):
                self.ST[i][j] = merge_method(self.ST[i - 1][j], self.ST[i - 1][j + (1 << i - 1)])

    def query(self, l, r):
        pos = self.note[r - l + 1]
        return self.merge_method(self.ST[pos][l], self.ST[pos][r - (1 << pos) + 1])

def main():
    t = I()
    n = II()
    strs = [I() for _ in range(n)]
    k = len(t)
    order = '#'.join((t, *strs))
    sa = suffix_array(order)
    lcp = construct_lcp(order, sa)
    pos = [-1] * len(sa)
    for (i, v) in enumerate(sa):
        pos[v] = i
    st = SparseTable(lcp, lambda x, y: x if x < y else y)
    diff = [0] * (len(sa) + 1)
    cur = k
    for i in range(n):
        cur += 1
        p = pos[cur]
        (l, r) = (0, p - 1)
        while l <= r:
            m = (l + r) // 2
            if st.query(m, p - 1) >= len(strs[i]):
                r = m - 1
            else:
                l = m + 1
        left = l
        (l, r) = (p + 1, len(sa) - 1)
        while l <= r:
            m = (l + r) // 2
            if st.query(p, m - 1) >= len(strs[i]):
                l = m + 1
            else:
                r = m - 1
        right = r
        diff[left] += 1
        diff[right + 1] -= 1
        cur += len(strs[i])
    for i in range(len(sa)):
        diff[i + 1] += diff[i]
    start_note = [0] * k
    for i in range(len(sa)):
        if sa[i] < k:
            start_note[sa[i]] = diff[i]
    order = '#'.join((t[::-1], *(s[::-1] for s in strs)))
    sa = suffix_array(order)
    lcp = construct_lcp(order, sa)
    pos = [-1] * len(sa)
    for (i, v) in enumerate(sa):
        pos[v] = i
    st = SparseTable(lcp, lambda x, y: x if x < y else y)
    diff = [0] * (len(sa) + 1)
    cur = k
    for i in range(n):
        cur += 1
        p = pos[cur]
        (l, r) = (0, p - 1)
        while l <= r:
            m = (l + r) // 2
            if st.query(m, p - 1) >= len(strs[i]):
                r = m - 1
            else:
                l = m + 1
        left = l
        (l, r) = (p + 1, len(sa) - 1)
        while l <= r:
            m = (l + r) // 2
            if st.query(p, m - 1) >= len(strs[i]):
                l = m + 1
            else:
                r = m - 1
        right = r
        diff[left] += 1
        diff[right + 1] -= 1
        cur += len(strs[i])
    for i in range(len(sa)):
        diff[i + 1] += diff[i]
    end_note = [0] * k
    for i in range(len(sa)):
        if sa[i] < k:
            end_note[k - 1 - sa[i]] = diff[i]
    print(sum((end_note[i] * start_note[i + 1] for i in range(k - 1))))
    return
t = 1
for _ in range(t):
    main()