SAMESAME - Editorial

editorial
,
1

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)