# SAMESAME - Editorial

Author: iceknight1093
Tester: pols_agyi_pols
Editorialist: iceknight1093

TBD

None

# PROBLEM:

Given two strings A and B, find the minimum possible Hamming distance between B and some substring of A.

# EXPLANATION:

The constraints are quite low, so nothing special needs to be done to solve this problem: simply implement what is asked for.

That is, do the following:

• Fix i, the left endpoint of the substring under consideration.
• Note that there should be at least M characters starting from i, which means i+M \leq N+1 must hold - that is, i \leq N-M+1.
• Then, for each j from 0 to M-1, compare A_{i+j} to B_{j+1}.
• This computes the Hamming distance between B and the substring of A starting at index i.

The answer is the minimum of this value across all starting indices i.
This can be implemented with a simple nested loop.

# TIME COMPLEXITY:

\mathcal{O}(N^2) per testcase.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n, m = map(int, input().split())
a = input()
b = input()
ans = m
for i in range(n-m+1):
difference = 0
for j in range(m): difference += a[i+j] != b[j]
ans = min(ans, difference)
print(ans)