Fuzzy Concatenation (Easy Version)

Research note: I checked the official Codeforces editorial, the Codeforces accepted-status listing, and maspy's round notes. The official page exposes solution code but no prose tutorial for E1/E2; maspy explicitly describes the bitset $O(nm/w)$ approach. The supplied statement is still the source of truth.

Call a string block good if it can be produced in one operation. For any position $p$ in $t$, define $best(p)$ as the maximum length $L$ such that $t[p..p+L-1]$ is good.

We greedily append the longest possible block from the current position. Generic greedy would be suspicious here, but this problem has the needed monotonicity. If $t[i..j]$ is good, then $t[i+1..j]$ is also good: take the same source substring from $s$, just without its first character. If the removed character was the modified one, then the suffix has zero mismatches. Therefore the optimal number of operations for suffixes of $t$ is nonincreasing as the starting index moves right. Landing farther right cannot make the rest harder. So choosing $best(p)$ is optimal.

Now compute $best(p)$.

For fixed $p$ and current length $L$, maintain two sets of starting positions $i$ in $s$:

• $E_L$: $s[i..i+L-1]$ equals $t[p..p+L-1]$ exactly.
• $F_L$: $s[i..i+L-1]$ differs from $t[p..p+L-1]$ in at most one position.

For $L=0$, every start in $s$ is both exact and fuzzy.

Suppose the next target character is $c=t[p+L]$. Let:

• $M_L(c)$ be the set of starts $i$ such that $i+L<n$ and $s[i+L]=c$.
• $V_L$ be the set of starts $i$ such that $i+L<n$.

Then:

$E_{L+1}=E_L\cap M_L(c)$

and

$F_{L+1}=(F_L\cap M_L(c))\cup(E_L\cap V_L).$

Why? For a length-$L+1$ fuzzy match, either the previous $L$ characters already had at most one mismatch and the new character matches, or the previous $L$ characters were exact and we spend the one allowed change on the new character. That's the whole trick.

Represent each set as a bitset over starts in $s$. Precompute $occ[c]$, where bit $i$ is set iff $s[i]=c$. Then $M_L(c)$ is $occ[c]$ shifted right by $L$, because bit $i$ should inspect $s[i+L]$. The set $V_L$ is the prefix mask containing the first $n-L$ bits.

For a fixed $p$, keep extending while $F_L$ is nonempty. The last successful $L$ is $best(p)$. Then move $p\leftarrow p+best(p)$ and count one operation.

Single-character blocks are always possible because $n\ge 1$: copy any one character from $s$ and change it if needed. So the answer always exists.

Each extension scans $\lceil n/64\rceil$ machine words. Across the greedy process, the tested prefixes cover $O(m)$ successful extensions plus at most one failed extension per operation, so the total time is

$O\left(\frac{nm}{64}\right)$

per test case, with $O(26\cdot n/64)$ memory.