Yet Another String Matching Problem (Codeforces 954I)
Tags: Math, fft

Suppose you have two strings s and t, and their length is equal. You may perform the following operation any number of times: choose two different characters c1 and c2, and replace every occurence of c1 in both strings with c2. Let's denote the distance between strings s and t as the minimum number of operations required to make these strings equal. For example, if s is abcd and t is ddcb, the distance between them is 2 — we may replace every occurence of a with b, so s becomes bbcd, and then we may replace every occurence of b with d, so both strings become ddcd.You are given two strings S and T. For every substring of S consisting of |T| characters you have to determine the distance between this substring and T.

Input: The first line contains the string S, and the second — the string T (1 ≤ |T| ≤ |S| ≤ 125000). Both strings consist of lowercase Latin letters from a to f.

Output: Print |S| - |T| + 1 integers. The i-th of these integers must be equal to the distance between the substring of S beginning at i-th index with length |T| and the string T.


Sample Inputs:
abcdefa
ddcb

Sample Outputs:
2 3 3 3

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def find_root(root_dict, x):
    L = []
    while x != root_dict[x]:
        L.append(x)
        x = root_dict[x]
    for y in L:
        root_dict[y] = x
    return x

def find_comp(pairs):
    root_dict = [i for i in range(6)]
    for i in range(36):
        if pairs[i] > 0:
            c1 = i // 6
            c2 = i % 6
            if c1 != c2:
                i1 = find_root(root_dict, c1)
                i2 = find_root(root_dict, c2)
                root_dict[i1] = i2
    comp_count = 0
    for i in range(6):
        if find_root(root_dict, i) == i:
            comp_count += 1
    return comp_count

def process(S, T):
    n = len(S)
    m = len(T)
    S1 = [[] for i in range(6)]
    T1 = [[] for i in range(6)]
    for i in range(n):
        ci = ord(S[i]) - ord('a')
        S1[ci].append(i)
    for i in range(m):
        ci = ord(T[i]) - ord('a')
        T1[ci].append(i)
    pairs = [[0 for j in range(36)] for i in range(n - m + 1)]
    for c1 in range(6):
        C1 = chr(c1 + ord('a'))
        for c2 in range(6):
            C2 = chr(c2 + ord('a'))
            c3 = 6 * c1 + c2
            if len(S1[c1]) <= 1000 and len(T1[c2]) <= 1000:
                for i in S1[c1]:
                    for j in T1[c2]:
                        if i >= j and i - j <= n - m:
                            pairs[i - j][c3] = 1
            elif len(S1[c1]) >= 1000:
                k1 = [i for i in range(n - m + 1)]
                for i in T1[c2]:
                    k2 = []
                    for k in k1:
                        if pairs[k][c3] == 0 and i + k <= n - 1 and (S[i + k] == C1):
                            pairs[k][c3] = 1
                        elif i + k <= n - 1:
                            k2.append(k)
                        elif i + k > n - 1:
                            break
                    k1 = k2
                    if len(k1) == 0:
                        break
            else:
                k1 = [i for i in range(n - m + 1)]
                m1 = len(S1[c1])
                for i1 in range(m1 - 1, -1, -1):
                    i = S1[c1][i1]
                    k2 = []
                    for k in k1:
                        if pairs[k][c3] == 0 and m - 1 >= i - k >= 0 and (T[i - k] == C2):
                            pairs[k][c3] = 1
                        elif i - k >= 0:
                            k2.append(k)
                        elif i - k < 0:
                            break
                    k1 = k2
                    if len(k1) == 0:
                        break
    answer = [6 - find_comp(pairs[i]) for i in range(n - m + 1)]
    answer = ' '.join(map(str, answer))
    sys.stdout.write(f'{answer}\n')
S = input().decode().strip()
T = input().decode().strip()
process(S, T)

Solution (Python):
from collections import defaultdict

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            (x, y) = (y, x)
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for (i, x) in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members
MOD = 998244353
IMAG = 911660635
IIMAG = 86583718
rate2 = (0, 911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 867605899, 0)
irate2 = (0, 86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 103369235, 0)
rate3 = (0, 372528824, 337190230, 454590761, 816400692, 578227951, 180142363, 83780245, 6597683, 70046822, 623238099, 183021267, 402682409, 631680428, 344509872, 689220186, 365017329, 774342554, 729444058, 102986190, 128751033, 395565204, 0)
irate3 = (0, 509520358, 929031873, 170256584, 839780419, 282974284, 395914482, 444904435, 72135471, 638914820, 66769500, 771127074, 985925487, 262319669, 262341272, 625870173, 768022760, 859816005, 914661783, 430819711, 272774365, 530924681, 0)

def butterfly(a):
    n = len(a)
    h = (n - 1).bit_length()
    le = 0
    while le < h:
        if h - le == 1:
            p = 1 << h - le - 1
            rot = 1
            for s in range(1 << le):
                offset = s << h - le
                for i in range(p):
                    l = a[i + offset]
                    r = a[i + offset + p] * rot
                    a[i + offset] = (l + r) % MOD
                    a[i + offset + p] = (l - r) % MOD
                rot *= rate2[(~s & -~s).bit_length()]
                rot %= MOD
            le += 1
        else:
            p = 1 << h - le - 2
            rot = 1
            for s in range(1 << le):
                rot2 = rot * rot % MOD
                rot3 = rot2 * rot % MOD
                offset = s << h - le
                for i in range(p):
                    a0 = a[i + offset]
                    a1 = a[i + offset + p] * rot
                    a2 = a[i + offset + p * 2] * rot2
                    a3 = a[i + offset + p * 3] * rot3
                    a1na3imag = (a1 - a3) % MOD * IMAG
                    a[i + offset] = (a0 + a2 + a1 + a3) % MOD
                    a[i + offset + p] = (a0 + a2 - a1 - a3) % MOD
                    a[i + offset + p * 2] = (a0 - a2 + a1na3imag) % MOD
                    a[i + offset + p * 3] = (a0 - a2 - a1na3imag) % MOD
                rot *= rate3[(~s & -~s).bit_length()]
                rot %= MOD
            le += 2

def butterfly_inv(a):
    n = len(a)
    h = (n - 1).bit_length()
    le = h
    while le:
        if le == 1:
            p = 1 << h - le
            irot = 1
            for s in range(1 << le - 1):
                offset = s << h - le + 1
                for i in range(p):
                    l = a[i + offset]
                    r = a[i + offset + p]
                    a[i + offset] = (l + r) % MOD
                    a[i + offset + p] = (l - r) * irot % MOD
                irot *= irate2[(~s & -~s).bit_length()]
                irot %= MOD
            le -= 1
        else:
            p = 1 << h - le
            irot = 1
            for s in range(1 << le - 2):
                irot2 = irot * irot % MOD
                irot3 = irot2 * irot % MOD
                offset = s << h - le + 2
                for i in range(p):
                    a0 = a[i + offset]
                    a1 = a[i + offset + p]
                    a2 = a[i + offset + p * 2]
                    a3 = a[i + offset + p * 3]
                    a2na3iimag = (a2 - a3) * IIMAG % MOD
                    a[i + offset] = (a0 + a1 + a2 + a3) % MOD
                    a[i + offset + p] = (a0 - a1 + a2na3iimag) * irot % MOD
                    a[i + offset + p * 2] = (a0 + a1 - a2 - a3) * irot2 % MOD
                    a[i + offset + p * 3] = (a0 - a1 - a2na3iimag) * irot3 % MOD
                irot *= irate3[(~s & -~s).bit_length()]
                irot %= MOD
            le -= 2

def multiply(s, t):
    n = len(s)
    m = len(t)
    if min(n, m) <= 60:
        a = [0] * (n + m - 1)
        for i in range(n):
            if i % 8 == 0:
                for j in range(m):
                    a[i + j] += s[i] * t[j]
                    a[i + j] %= MOD
            else:
                for j in range(m):
                    a[i + j] += s[i] * t[j]
        return [x % MOD for x in a]
    a = s.copy()
    b = t.copy()
    z = 1 << (n + m - 2).bit_length()
    a += [0] * (z - n)
    b += [0] * (z - m)
    butterfly(a)
    butterfly(b)
    for i in range(z):
        a[i] *= b[i]
        a[i] %= MOD
    butterfly_inv(a)
    a = a[:n + m - 1]
    iz = pow(z, MOD - 2, MOD)
    return [v * iz % MOD for v in a]
s = input()
t = input()
n = len(s)
m = len(t)
k = n - m + 1
pair = [[] for i in range(k)]
for i in range(6):
    for j in range(6):
        if i == j:
            continue
        a = []
        b = []
        for x in s:
            if ord(x) - 97 == i:
                a.append(1)
            else:
                a.append(0)
        for x in t:
            if ord(x) - 97 == j:
                b.append(1)
            else:
                b.append(0)
        c = multiply(a, b[::-1])
        for x in range(k):
            if c[m - 1 + x] > 0:
                pair[x].append((i, j))
ans = [0] * k
for i in range(k):
    uf = UnionFind(6)
    for (x, y) in pair[i]:
        uf.union(x, y)
    g = uf.all_group_members()
    for j in g:
        ans[i] += len(g[j]) - 1
print(*ans)

Solution (Python):
from io import BytesIO, IOBase
import sys
import os
import bisect
import math
import random
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
from typing import *

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')
BUFSIZE = 4096

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 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))

    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()
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

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 GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')
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

class UnionFind:

    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, a):
        a = self.parent[a]
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            (self.parent[acopy], acopy) = (a, self.parent[acopy])
        return a

    def merge(self, a, b):
        (pa, pb) = (self.find(a), self.find(b))
        if pa == pb:
            return False
        self.parent[pb] = pa
        return True

class FFT:

    def __init__(self, MOD=998244353):
        FFT.MOD = MOD
        g = self.primitive_root_constexpr()
        ig = pow(g, FFT.MOD - 2, FFT.MOD)
        FFT.W = [pow(g, FFT.MOD - 1 >> i, FFT.MOD) for i in range(30)]
        FFT.iW = [pow(ig, FFT.MOD - 1 >> i, FFT.MOD) for i in range(30)]

    def primitive_root_constexpr(self):
        if FFT.MOD == 998244353:
            return 3
        elif FFT.MOD == 200003:
            return 2
        elif FFT.MOD == 167772161:
            return 3
        elif FFT.MOD == 469762049:
            return 3
        elif FFT.MOD == 754974721:
            return 11
        divs = [0] * 20
        divs[0] = 2
        cnt = 1
        x = (FFT.MOD - 1) // 2
        while x % 2 == 0:
            x //= 2
        i = 3
        while i * i <= x:
            if x % i == 0:
                divs[cnt] = i
                cnt += 1
                while x % i == 0:
                    x //= i
            i += 2
        if x > 1:
            divs[cnt] = x
            cnt += 1
        g = 2
        while 1:
            ok = True
            for i in range(cnt):
                if pow(g, (FFT.MOD - 1) // divs[i], FFT.MOD) == 1:
                    ok = False
                    break
            if ok:
                return g
            g += 1

    def fft(self, k, f):
        for l in range(k, 0, -1):
            d = 1 << l - 1
            U = [1]
            for i in range(d):
                U.append(U[-1] * FFT.W[l] % FFT.MOD)
            for i in range(1 << k - l):
                for j in range(d):
                    s = i * 2 * d + j
                    (f[s], f[s + d]) = ((f[s] + f[s + d]) % FFT.MOD, U[j] * (f[s] - f[s + d]) % FFT.MOD)

    def ifft(self, k, f):
        for l in range(1, k + 1):
            d = 1 << l - 1
            for i in range(1 << k - l):
                u = 1
                for j in range(i * 2 * d, (i * 2 + 1) * d):
                    f[j + d] *= u
                    (f[j], f[j + d]) = ((f[j] + f[j + d]) % FFT.MOD, (f[j] - f[j + d]) % FFT.MOD)
                    u = u * FFT.iW[l] % FFT.MOD

    def convolve(self, A, B):
        n0 = len(A) + len(B) - 1
        k = n0.bit_length()
        n = 1 << k
        A += [0] * (n - len(A))
        B += [0] * (n - len(B))
        self.fft(k, A)
        self.fft(k, B)
        A = [a * b % FFT.MOD for (a, b) in zip(A, B)]
        self.ifft(k, A)
        inv = pow(n, FFT.MOD - 2, FFT.MOD)
        A = [a * inv % FFT.MOD for a in A]
        del A[n0:]
        return A
nums1 = list(map(lambda x: ord(x) - ord('a'), I()))
nums2 = list(map(lambda x: ord(x) - ord('a'), I()))
(n, m) = (len(nums1), len(nums2))
unions = [UnionFind(6) for _ in range(n - m + 1)]
fft = FFT()
for i in range(6):
    for j in range(6):
        if i != j:
            v1 = [1 if x == i else 0 for x in nums1]
            v2 = [1 if x == j else 0 for x in nums2]
            v2.reverse()
            res = fft.convolve(v1, v2)
            for idx in range(n - m + 1):
                if res[idx + m - 1]:
                    unions[idx].merge(i, j)
ans = []
for i in range(n - m + 1):
    ans.append(6 - len({unions[i].find(x) for x in range(6)}))
print(*ans)