Prefix Function Queries (Codeforces 1721E)
Tags: DP, string suffix structures

You are given a string $$$s$$$, consisting of lowercase Latin letters.You are asked $$$q$$$ queries about it: given another string $$$t$$$, consisting of lowercase Latin letters, perform the following steps:  concatenate $$$s$$$ and $$$t$$$;  calculate the prefix function of the resulting string $$$s+t$$$;  print the values of the prefix function on positions $$$|s|+1, |s|+2, \dots, |s|+|t|$$$ ($$$|s|$$$ and $$$|t|$$$ denote the lengths of strings $$$s$$$ and $$$t$$$, respectively);  revert the string back to $$$s$$$. The prefix function of a string $$$a$$$ is a sequence $$$p_1, p_2, \dots, p_{|a|}$$$, where $$$p_i$$$ is the maximum value of $$$k$$$ such that $$$k < i$$$ and $$$a[1..k]=a[i-k+1..i]$$$ ($$$a[l..r]$$$ denotes a contiguous substring of a string $$$a$$$ from a position $$$l$$$ to a position $$$r$$$, inclusive). In other words, it's the longest proper prefix of the string $$$a[1..i]$$$ that is equal to its suffix of the same length.

Input: The first line contains a non-empty string $$$s$$$ ($$$1 \le |s| \le 10^6$$$), consisting of lowercase Latin letters.The second line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.Each of the next $$$q$$$ lines contains a query: a non-empty string $$$t$$$ ($$$1 \le |t| \le 10$$$), consisting of lowercase Latin letters.

Output: For each query, print the values of the prefix function of a string $$$s+t$$$ on positions $$$|s|+1, |s|+2, \dots, |s|+|t|$$$.


Sample Inputs:
aba
6
caba
aba
bababa
aaaa
b
forces

aacba
4
aaca
cbbb
aab
ccaca

Sample Outputs:
0 1 2 3 
1 2 3 
2 3 4 5 6 7 
1 1 1 1 
2 
0 0 0 0 0 0

2 2 3 1 
0 0 0 0 
2 2 0 
0 0 1 0 1

Solution (Python):
""""""
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write

def debug(*args):
    if os.environ.get('debug') in [None, '0']:
        return
    from inspect import currentframe, getframeinfo
    from re import search
    frame = currentframe().f_back
    s = getframeinfo(frame).code_context[0]
    r = search('\\((.*)\\)', s).group(1)
    vnames = r.split(', ')
    var_and_vals = [f'{var}={val}' for (var, val) in zip(vnames, args)]
    prefix = f'{currentframe().f_back.f_lineno:02d}: '
    print(f"{prefix}{', '.join(var_and_vals)}")
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        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

class IntKeyDict(dict):
    from random import randrange
    rand = randrange(1 << 62)

    def __setitem__(self, k, v):
        super().__setitem__(k ^ self.rand, v)

    def __getitem__(self, k):
        return super().__getitem__(k ^ self.rand)

    def __contains__(self, k):
        return super().__contains__(k ^ self.rand)

    def __repr__(self):
        return str({k: v for (k, v) in self.items()})

    def get(self, k, default=None):
        return super().get(k ^ self.rand, default)

    def keys(self):
        return [k ^ self.rand for k in super().keys()]

    def items(self):
        return [(k ^ self.rand, v) for (k, v) in super().items()]
INF = float('inf')

def main():
    S = input().decode().strip()
    Q = int(input())
    N = len(S)
    lps = [0] * (N + 10)
    dfa = [[0] * (N + 10) for _ in range(26)]
    dfa[ord(S[0]) - ord('a')][0] = 1
    for i in range(1, N):
        for c in range(26):
            if c == ord(S[i]) - ord('a'):
                dfa[c][i] = i + 1
                lps[i] = dfa[c][lps[i - 1]]
            else:
                dfa[c][i] = dfa[c][lps[i - 1]]
    for _ in range(Q):
        T = input().decode().strip()
        M = len(T)
        for i in range(N, N + M):
            for c in range(26):
                if c == ord(T[i - N]) - ord('a'):
                    dfa[c][i] = i + 1
                    lps[i] = dfa[c][lps[i - 1]]
                else:
                    dfa[c][i] = dfa[c][lps[i - 1]]
        print(*lps[N:N + M])
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
s = input().strip()
l = len(s)
(d, p) = ([], [0])
d.append([1 if s[0] == chr(x + 97) else 0 for x in range(26)])
for (idx, i) in enumerate(s):
    if idx == 0:
        continue
    x = ord(i) - 97
    d.append(d[p[idx - 1]][:])
    d[idx][x] = idx + 1
    p.append(d[p[idx - 1]][x])
for i in range(10):
    p.append(0)
    d.append([])
for i in range(int(input())):
    for (idx, t) in enumerate(input().strip()):
        (x, pos) = (ord(t) - 97, idx + l)
        d[pos] = d[p[pos - 1]][:]
        d[pos][x] = pos + 1
        p[pos] = d[p[pos - 1]][x]
    print(*p[l:l + idx + 1])

Solution (Python):
import io, os, sys
import random
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def add_char(maxsuf, dp, index, c):
    prelength = maxsuf[index[0] - 1]
    for i in range(26):
        dp[index[0]][i] = dp[prelength][i]
    dp[index[0]][c] = index[0] + 1
    maxsuf[index[0]] = dp[prelength][c]
    index[0] += 1

def main(t):
    s = input().decode('utf-8')[:-2]
    n = len(s)
    dp = [[0] * 26 for _ in range(n + 11)]
    maxsuf = [0] * (n + 11)
    dp[0][ord(s[0]) - 97] = 1
    index = [1]
    while index[0] < n:
        add_char(maxsuf, dp, index, ord(s[index[0]]) - 97)
    q = int(input())
    for _ in range(q):
        news = input().decode('utf-8')[:-2]
        index[0] = n
        ans = []
        while index[0] < n + len(news):
            add_char(maxsuf, dp, index, ord(news[index[0] - n]) - 97)
            ans.append(maxsuf[index[0] - 1])
        ans = ' '.join(map(str, ans))
        sys.stdout.write(ans + '\n')
T = 1
t = 1
while t <= T:
    main(t)
    t += 1