Substring Search
You are given a permutation $$$p$$$ consisting of exactly $$$26$$$ integers from $$$1$$$ to $$$26$$$ (since it is a permutation, each integer from $$$1$$$ to $$$26$$$ occurs in $$$p$$$ exactly once) and two strings $$$s$$$ and $$$t$$$ consisting of lowercase Latin letters.A substring $$$t'$$$ of string $$$t$$$ is an occurence of string $$$s$$$ if the following conditions are met:  $$$|t'| = |s|$$$;  for each $$$i \in [1, |s|]$$$, either $$$s_i = t'_i$$$, or $$$p_{idx(s_i)} = idx(t'_i)$$$, where $$$idx(c)$$$ is the index of character $$$c$$$ in Latin alphabet ($$$idx(\text{a}) = 1$$$, $$$idx(\text{b}) = 2$$$, $$$idx(\text{z}) = 26$$$). For example, if $$$p_1 = 2$$$, $$$p_2 = 3$$$, $$$p_3 = 1$$$, $$$s = \text{abc}$$$, $$$t = \text{abcaaba}$$$, then three substrings of $$$t$$$ are occurences of $$$s$$$ (they are $$$t' = \text{abc}$$$, $$$t' = \text{bca}$$$ and $$$t' = \text{aba}$$$).For each substring of $$$t$$$ having length equal to $$$|s|$$$, check if it is an occurence of $$$s$$$.
The first line contains $$$26$$$ integers $$$p_1$$$, $$$p_2$$$, ..., $$$p_{26}$$$ ($$$1 \le p_i \le 26$$$, all these integers are pairwise distinct).The second line contains one string $$$s$$$, and the third line contains one string $$$t$$$ ($$$2 \le |s| \le |t| \le 2 \cdot 10^5$$$) both consisting of lowercase Latin letters.
Print a string of $$$|t| - |s| + 1$$$ characters, each character should be either 0 or 1. The $$$i$$$-th character should be 1 if and only if the substring of $$$t$$$ starting with the $$$i$$$-th character and ending with the $$$(i + |s| - 1)$$$-th character (inclusive) is an occurence of $$$s$$$.
import random
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
mod = 998244353
r = [pow(3, mod >> i, mod) for i in range(23)]
ir = [pow(i, mod - 2, mod) for i in r]
u = [0] * (1 << 23)

def convolve(f, g):
    (lf, lg) = (len(f), len(g))
    c = lf + lg - 1
    x = c.bit_length()
    l = 1 << x
    for i in range(lf):
        u[i] = f[i]
    for i in range(lf, l):
        u[i] = 0
    for i in range(lg):
        u[i ^ l] = g[i]
    for i in range(lg, l):
        u[i ^ l] = 0
    m = l >> 1
    for k in range(x, 0, -1):
        r0 = r[k]
        for i in range(0, l, m << 1):
            y = 1
            for j in range(i, m + i):
                (u[j], u[j + m]) = ((u[j] + u[j + m]) % mod, (u[j] - u[j + m]) * y % mod)
                (u[j + l], u[j + m + l]) = ((u[j + l] + u[j + m + l]) % mod, (u[j + l] - u[j + m + l]) * y % mod)
                y = y * r0 % mod
        m >>= 1
    for i in range(l):
        u[i] = u[i] * u[i ^ l] % mod
    m = 1
    for k in range(1, x + 1):
        r0 = ir[k]
        for i in range(0, l, m << 1):
            y = 1
            for j in range(i, m + i):
                (u[j], u[j + m]) = ((u[j] + u[j + m] * y) % mod, (u[j] - u[j + m] * y) % mod)
                y = y * r0 % mod
        m <<= 1
    il = pow(l, mod - 2, mod)
    for i in range(c):
        u[i] = u[i] * il % mod
    return
p = [0] + list(map(int, input().split()))
s = list(input().rstrip())
t = list(input().rstrip())
(s, t) = ([i - 96 for i in s], [i - 96 for i in t])
(n, m) = (len(s), len(t))
r1 = [random.randint(1, mod - 1) for _ in range(27)]
s2 = [r1[p[i]] for i in s]
s = [r1[i] for i in s]
t = [r1[i] for i in t]
x = [0] * (m + 1)
for i in range(m):
    x[i + 1] = t[i] * t[i] % mod + x[i]
ans = ['1'] * (m - n + 1)
(f, g) = ([(i + j) % mod for (i, j) in zip(s, s2)], t[::-1])
convolve(f, g)
v = 0
for (i, j) in zip(s, s2):
    v += i * j % mod
for i in range(m - n + 1):
    if (x[i + n] - x[i] + v - u[m - i - 1]) % mod:
        ans[i] = '0'
sys.stdout.write(''.join(ans))
import random
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
mod = 998244353
r = [pow(3, mod >> i, mod) for i in range(23)]
ir = [pow(i, mod - 2, mod) for i in r]
u = [0] * (1 << 23)

def convolve(f, g):
    (lf, lg) = (len(f), len(g))
    c = lf + lg - 1
    x = c.bit_length()
    l = 1 << x
    for i in range(lf):
        u[i] = f[i]
    for i in range(lf, l):
        u[i] = 0
    for i in range(lg):
        u[i ^ l] = g[i]
    for i in range(lg, l):
        u[i ^ l] = 0
    m = l >> 1
    for k in range(x, 0, -1):
        r0 = r[k]
        for i in range(0, l, m << 1):
            y = 1
            for j in range(i, m + i):
                (u[j], u[j + m]) = ((u[j] + u[j + m]) % mod, (u[j] - u[j + m]) * y % mod)
                (u[j + l], u[j + m + l]) = ((u[j + l] + u[j + m + l]) % mod, (u[j + l] - u[j + m + l]) * y % mod)
                y = y * r0 % mod
        m >>= 1
    for i in range(l):
        u[i] = u[i] * u[i ^ l] % mod
    m = 1
    for k in range(1, x + 1):
        r0 = ir[k]
        for i in range(0, l, m << 1):
            y = 1
            for j in range(i, m + i):
                (u[j], u[j + m]) = ((u[j] + u[j + m] * y) % mod, (u[j] - u[j + m] * y) % mod)
                y = y * r0 % mod
        m <<= 1
    il = pow(l, mod - 2, mod)
    for i in range(c):
        u[i] = u[i] * il % mod
    return
p = [0] + list(map(int, input().split()))
s = list(input().rstrip())
t = list(input().rstrip())
(s, t) = ([i - 96 for i in s], [i - 96 for i in t])
(n, m) = (len(s), len(t))
r1 = [random.randint(1, mod - 1) for _ in range(27)]
s2 = [r1[p[i]] for i in s]
s = [r1[i] for i in s]
t = [r1[i] for i in t]
x = [0] * (m + 1)
for i in range(m):
    x[i + 1] = t[i] * t[i] % mod + x[i]
ans = ['1'] * (m - n + 1)
(f, g) = ([(i + j) % mod for (i, j) in zip(s, s2)], t[::-1])
convolve(f, g)
v = 0
for (i, j) in zip(s, s2):
    v += i * j % mod
for i in range(m - n + 1):
    if (x[i + n] - x[i] + v - u[m - i - 1]) % mod:
        ans[i] = '0'
sys.stdout.write(''.join(ans))
import random
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
mod = 998244353
r = [pow(3, mod >> i, mod) for i in range(23)]
ir = [pow(i, mod - 2, mod) for i in r]
u = [0] * (1 << 23)

def convolve(f, g):
    (lf, lg) = (len(f), len(g))
    c = lf + lg - 1
    x = c.bit_length()
    l = 1 << x
    for i in range(lf):
        u[i] = f[i]
    for i in range(lf, l):
        u[i] = 0
    for i in range(lg):
        u[i ^ l] = g[i]
    for i in range(lg, l):
        u[i ^ l] = 0
    m = l >> 1
    for k in range(x, 0, -1):
        r0 = r[k]
        for i in range(0, l, m << 1):
            y = 1
            for j in range(i, m + i):
                (u[j], u[j + m]) = ((u[j] + u[j + m]) % mod, (u[j] - u[j + m]) * y % mod)
                (u[j + l], u[j + m + l]) = ((u[j + l] + u[j + m + l]) % mod, (u[j + l] - u[j + m + l]) * y % mod)
                y = y * r0 % mod
        m >>= 1
    for i in range(l):
        u[i] = u[i] * u[i ^ l] % mod
    m = 1
    for k in range(1, x + 1):
        r0 = ir[k]
        for i in range(0, l, m << 1):
            y = 1
            for j in range(i, m + i):
                (u[j], u[j + m]) = ((u[j] + u[j + m] * y) % mod, (u[j] - u[j + m] * y) % mod)
                y = y * r0 % mod
        m <<= 1
    return
p = [0] + list(map(int, input().split()))
s = list(input().rstrip())
t = list(input().rstrip())
(s, t) = ([i - 96 for i in s], [i - 96 for i in t])
(n, m) = (len(s), len(t))
r1 = [random.randint(1, mod - 1) for _ in range(27)]
s2 = [r1[p[i]] for i in s]
s = [r1[i] for i in s]
t = [r1[i] for i in t]
x = [s[i] * s2[i] % mod for i in range(n)]
ans = ['1'] * (m - n + 1)
(f, g1) = ([0] * n, t[::-1])
g2 = [i * i % mod for i in g1]
w = 2097152
l = 1 << (len(s) + len(g1) - 1).bit_length()
z = [1] * (n + 1)
for i in range(n):
    f[i] = 0 if not z[i + 1] else (s[i] + s2[i]) % mod
convolve(f, g1)
for i in range(n + m):
    u[i ^ w] = u[i]
for i in range(n):
    f[i] = z[i + 1]
convolve(f, g2)
v = 0
for i in range(n):
    v += z[i + 1] * x[i]
v = v % mod * l % mod
for i in range(m - n + 1):
    if (u[m - i - 1] + v - u[m - i + w - 1]) % mod:
        ans[i] = '0'
sys.stdout.write(''.join(ans))