PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: pols_agyi_pols
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
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)