AtCoder Beginner Contest 177 - Substring

Given are two strings S and T.
Let us change some of the characters in S so that T will be a substring of S.
At least how many characters do we need to change?
Here, a substring is a consecutive subsequence. For example, xxx is a substring of yxxxy, but not a substring of xxyxx.

-----Constraints-----
 - The lengths of S and T are each at least 1 and at most 1000.
 - The length of T is at most that of S.
 - S and T consist of lowercase English letters.

-----Input-----
Input is given from Standard Input in the following format:
S
T

-----Output-----
Print the minimum number of characters in S that need to be changed.

-----Sample Input-----
cabacc
abc

-----Sample Output-----
1

For example, changing the fourth character a in S to c will match the second through fourth characters in S to T.
Since S itself does not have T as its substring, this number of changes - one - is the minimum needed.

Source: atcoder | Difficulty: EASY


Solutions:
S = input()
T = input()
ans = 0
for i in range(len(S) - len(T) + 1):
	k = 0
	for j in range(len(T)):
		if S[i + j] == T[j]:
			k += 1
	ans = max(k, ans)
print(len(T) - ans)


import sys
S = input()
T = input()
ans = len(T)
for i in range(len(S) - len(T) + 1):
	count = 0
	for j in range(len(T)):
		if S[i + j] == T[j]:
			count += 1
	ans = min(ans, len(T) - count)
print(ans)


S = list(input())
T = list(input())
ans = len(T)
for i in range(len(S) - len(T) + 1):
	tot = 0
	for j in range(len(T)):
		if S[i + j] != T[j]:
			tot += 1
	ans = min(ans, tot)
print(ans)


s = input()
t = input()
n = len(s)
m = len(t)
print(min([sum([s[i + j] != t[j] for j in range(m)]) for i in range(n - m + 1)]))


S = str(input())
T = str(input())
if T in S:
	print(0)
	return
(max_char_cnt, substr) = (0, '')
for i in range(len(S) - len(T) + 1):
	substr = S[i:i + len(T)]
	same_char_cnt = 0
	for (s, t) in zip(substr, T):
		if s == t:
			same_char_cnt += 1
	max_char_cnt = max(max_char_cnt, same_char_cnt)
	if len(T) - max_char_cnt == 1:
		break
print(len(T) - max_char_cnt)


(s, t) = [input() for i in range(2)]
c = []
for i in range(len(s) - len(t) + 1):
	d = len(t)
	for (a, b) in zip(s[i:], t):
		if a == b:
			d -= 1
	c.append(d)
print(min(c))


(s, t) = (input(), input())
print(min((sum((a != b for (a, b) in zip(s[i:], t))) for i in range(len(s) - len(t) + 1))))


s = input()
t = input()
mc = 0
for i in range(len(s) - len(t) + 1):
	c = 0
	for j in range(len(t)):
		if s[i + j] == t[j]:
			c += 1
	mc = max(c, mc)
print(len(t) - mc)


s = input()
t = input()
ans = 10 ** 9
for i in range(len(s) - len(t) + 1):
	now = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			now += 1
	ans = min(now, ans)
print(ans)


s = input()
t = input()
ls = len(s)
lt = len(t)
mc = lt
for i in range(ls - lt + 1):
	c = 0
	for j in range(lt):
		if s[i + j] != t[j]:
			c += 1
	mc = min(mc, c)
print(mc)


def compare_s(s1, s2):
	ret = 0
	for (i1, i2) in zip(s1, s2):
		if i1 != i2:
			ret += 1
	return ret
s = input()
t = input()
min_ = 1001
for i in range(len(s) - len(t) + 1):
	temp = compare_s(t, s[i:])
	if temp < min_:
		min_ = temp
print(min_)


s = input()
t = input()
res = []
for i in range(len(s) - len(t) + 1):
	x = s[i:i + len(t)]
	count = sum((1 for (a, b) in zip(t, x) if a != b))
	res.append(count)
print(min(res))


(S, T) = (input(), input())
res = n = len(T)
m = len(S)
for i in range(m - n + 1):
	c = 0
	for k in range(n):
		if S[i + k] != T[k]:
			c += 1
	res = min(res, c)
print(res)


s = input()
t = input()
ans = []
for i in range(len(s) - len(t) + 1):
	l = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			l += 1
	ans.append(l)
print(min(ans))


s = input()
t = input()
ans = len(t)
for i in range(len(s) - len(t) + 1):
	count = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			count += 1
	ans = min(ans, count)
print(ans)


s = input()
t = input()
ls = []
for i in range(len(s) - len(t) + 1):
	ls.append(s[i:i + len(t)])
now = 0
minimum = len(t)
for i in range(len(ls)):
	now = 0
	for j in range(len(t)):
		if t[j] == ls[i][j]:
			now += 1
	if len(t) - now < minimum:
		minimum = len(t) - now
print(minimum)


a = input()
b = input()
T = 1000
for i in range(len(a) - len(b) + 1):
	ans = 0
	for j in range(len(b)):
		if a[i + j] != b[j]:
			ans += 1
	T = min(T, ans)
print(T)


s = input()
t = input()
m = len(s)
for i in range(len(s) - len(t) + 1):
	c = 0
	for j in range(len(t)):
		if t[j] != s[i + j]:
			c += 1
	m = min(m, c)
print(m)


S = input()
T = input()
print(min([sum(map(lambda x: x[0] != x[1], zip(S[i:i + len(T)], T))) for i in range(1 + len(S) - len(T))]))


S = input()
T = input()
x = 0
for i in range(len(S) - len(T) + 1):
	y = 0
	for j in range(len(T)):
		if S[i + j] == T[j]:
			y += 1
	if y > x:
		x = y
print(len(T) - x)


S = str(input())
T = str(input())
ls = len(S)
lt = len(T)
m = 0
for i in range(ls - lt + 1):
	A = S[i:i + lt]
	a = 0
	for (s, t) in zip(A, T):
		if s == t:
			a += 1
	m = max(m, a)
print(lt - m)


s = input()
t = input()
(T, S) = (len(t), len(s))
ans = T
for i in range(S - T + 1):
	tmp = [c1 != c2 for (c1, c2) in zip(s[i:i + T], t)].count(True)
	ans = min(ans, tmp)
print(ans)


s = input()
t = input()
n = len(s)
m = len(t)
ans = m
for i in range(n - m + 1):
	p = 0
	for j in range(m):
		if s[i + j] != t[j]:
			p += 1
	if p < ans:
		ans = p
print(ans)


S = input()
T = input()
data = []
for i in range(len(S) - len(T) + 1):
	count = 0
	for j in range(len(T)):
		if S[i + j] != T[j]:
			count += 1
	data.append(count)
print(min(data))


s = input()
t = input()
x = 1001
for i in range(len(s) - len(t) + 1):
	cnt = 0
	for j in range(len(t)):
		if s[j + i] != t[j]:
			cnt += 1
	x = min(x, cnt)
print(x)


S = input()
T = input()
ans = len(T)
for i in range(len(S) - len(T) + 1):
	ans = min(ans, sum([1 for j in range(len(T)) if T[j] != S[i + j]]))
print(ans)


from sys import stdin
S = stdin.readline().rstrip()
T = stdin.readline().rstrip()
(ls, lt) = (len(S), len(T))
ans = ls
for i in range(0, ls - lt + 1):
	diff = 0
	for j in range(lt):
		if T[j] != S[i + j]:
			diff += 1
	ans = min(ans, diff)
print(ans)


S = input()
T = input()
max_match = 0
temp_match = 0
for i in range(len(S) - len(T) + 1):
	for j in range(len(T)):
		if S[i + j] == T[j]:
			temp_match += 1
	if temp_match > max_match:
		max_match = temp_match
	temp_match = 0
print(len(T) - max_match)


S = input()
T = input()
ans = float('inf')
for start in range(len(S) - len(T) + 1):
	ans = min(ans, sum((s != t for (s, t) in zip(S[start:], T))))
print(ans)


s = list(input())
t = list(input())
n = len(s) - len(t) + 1
ans = 0
for i in range(n):
	count = 0
	for g in range(len(t)):
		if s[g + i] == t[g]:
			count += 1
	if count >= ans:
		ans = count
print(len(t) - ans)


S = input()
T = input()
ans = len(T)
for i in range(len(S) - len(T) + 1):
	a = 0
	for j in range(len(T)):
		if S[i + j] != T[j]:
			a += 1
	ans = min(ans, a)
print(ans)


S = input()
T = input()
c = 0
l = []
for i in range(len(S) - len(T) + 1):
	for k in range(len(T)):
		if T[k] != S[k + i]:
			c += 1
	l.append(c)
	c = 0
print(min(l))


s = [x for x in input()]
t = [x for x in input()]
u = list()
for i in range(len(s) - len(t) + 1):
	count = 0
	for j in range(len(t)):
		if s[i + j] == t[j]:
			continue
		if s[i + j] != t[j]:
			count += 1
	u.append(count)
u.sort()
print(u[0])


s = input()
t = input()
string_list = []
for i in range(len(s) - len(t) + 1):
	string_list.append(s[i:i + len(t)])
count = 0
max_value = 0
for j in range(len(string_list)):
	for i in range(len(t)):
		if string_list[j][i] == t[i]:
			count += 1
		if max_value < count:
			max_value = count
	count = 0
print(len(t) - max_value)


S = input()
T = input()
P = 10 ** 18
Q = 0
for i in range(len(S) - len(T) + 1):
	Q = 0
	for j in range(len(T)):
		if T[j] != S[i + j]:
			Q += 1
	P = min(P, Q)
print(P)


s = input()
t = input()
min_cnt = 10000
for i in range(len(s) - len(t) + 1):
	cnt = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			cnt += 1
	if cnt < min_cnt:
		min_cnt = cnt
print(min_cnt)


S = input()
T = input()
N = len(S)
M = len(T)
cnt_min = M
for i in range(N - M + 1):
	count = 0
	for j in range(M):
		if S[i + j] != T[j]:
			count += 1
	if count < cnt_min:
		cnt_min = count
print(cnt_min)


s = input()
t = input()
ans = len(t)
for i in range(len(s) - len(t) + 1):
	p = s[i:i + len(t)]
	cur = 0
	for j in range(len(t)):
		if t[j] != p[j]:
			cur += 1
	ans = min(ans, cur)
print(ans)


s = input()
t = input()
ans = 1000000000.0
for i in range(len(s) - len(t) + 1):
	cnt = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			cnt += 1
	ans = min(ans, cnt)
print(ans)


s = input()
t = input()
a = 1000
for i in range(len(s) - len(t) + 1):
	c = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			c += 1
	a = min(a, c)
print(a)


s = list(input())
t = list(input())
ss = len(s)
tt = len(t)
ans = tt
for i in range(ss - tt + 1):
	u = s[i:i + tt]
	cnt = 0
	for j in range(tt):
		if u[j] == t[j]:
			cnt += 1
			ans_ = tt - cnt
			ans = min(ans, ans_)
print(ans)


s = input()
t = input()
a = len(t)
for i in range(len(s) - len(t) + 1):
	a = min(a, sum([x[0] != x[1] for x in zip(t, s[i:])]))
print(a)


(s, t) = (input(), input())
print(min((sum((x != y for (x, y) in zip(s[i:], t))) for i in range(len(s) - len(t) + 1))))


S = input()
T = input()
a = 10000
for i in range(len(S) - len(T) + 1):
	c = 0
	for j in range(len(T)):
		if T[j] != S[i + j]:
			c += 1
	if c < a:
		a = c
print(a)


S = input()
T = input()
ans = len(T)
for start in range(len(S) - len(T) + 1):
	diff = 0
	for i in range(len(T)):
		if T[i] != S[start + i]:
			diff += 1
	ans = min(ans, diff)
print(ans)


s = input()
t = input()
n = len(s)
k = len(t)
an = k
for i in range(n - k + 1):
	a = s[i:i + k]
	ct = 0
	for j in range(k):
		if a[j] != t[j]:
			ct += 1
	an = min(an, ct)
print(an)


import sys

def input():
	return sys.stdin.readline().strip()
sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7
INF = float('inf')

def main():
	S = input()
	T = input()
	answer = INF
	for i in range(len(S) - len(T) + 1):
		tmp = 0
		for j in range(len(T)):
			if S[i + j] != T[j]:
				tmp += 1
		answer = min(answer, tmp)
	print(answer)

def __starting_point():
	main()
__starting_point()


s = list(input())
t = list(input())
A = 10000
for i in range(len(s) - len(t) + 1):
	u = s[i:i + len(t)]
	a = 0
	for j in range(len(t)):
		if u[j] != t[j]:
			a += 1
	A = min(A, a)
print(A)


S = input()
T = input()
ans = 1001
for i in range(len(S) - len(T) + 1):
	wk = 0
	for j in range(len(T)):
		if S[i + j] != T[j]:
			wk += 1
	ans = min(wk, ans)
print(ans)


S = input()
T = input()
N = len(S)
NP = len(T)
M = len(T)
for i in range(N - M + 1):
	cnt = 0
	for j in range(M):
		if T[j] == S[j + i]:
			cnt += 1
	if NP > M - cnt:
		NP = M - cnt
print(NP)


S = input()
T = input()
ans = []
for i in range(len(S) - len(T) + 1):
	x = 0
	for j in range(len(T)):
		if S[i + j] != T[j]:
			x += 1
	ans.append(x)
print(min(ans))


s = input()
t = input()
k = len(t)
for i in range(len(s) - len(t) + 1):
	p = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			p += 1
	if k > p:
		k = p
print(k)


S = input()
T = input()
ls = len(S)
lt = len(T)
ans = float('inf')
for i in range(0, ls - lt + 1):
	ans = min(ans, sum([l != m for (l, m) in zip(S[i:i + lt], T)]))
print(ans)


S = input()
T = input()
x = len(S)
y = len(T)
l = []
for i in range(x - (y - 1)):
	s = 0
	for j in range(y):
		if S[j + i] == T[j]:
			s += 1
	l.append(y - s)
print(min(l))


s = input()
t = input()
mx = 0
for i in range(len(s) - len(t) + 1):
	sm = 0
	for j in range(len(t)):
		if s[i + j] == t[j]:
			sm += 1
	mx = max(sm, mx)
print(len(t) - mx)


x = input()
y = input()
dist = len(x)
for a in range(len(x) - len(y) + 1):
	tmp = 0
	for b in range(len(y)):
		if x[b + a] != y[b]:
			tmp += 1
	if dist > tmp:
		dist = tmp
print(dist)


S = input()
T = input()
lens = len(S)
lent = len(T)
mincnt = lent
if lens == lent:
	if S == T:
		mincnt = 0
	else:
		cnt = 0
		for i in range(lent):
			if S[i] != T[i]:
				cnt += 1
		mincnt = cnt
else:
	for i in range(lens - lent):
		cnt = 0
		for j in range(lent):
			if S[i + j] != T[j]:
				cnt += 1
		if cnt < mincnt:
			mincnt = cnt
print(mincnt)


S = input()
T = input()
ans = 1000
for i in range(len(S) - len(T) + 1):
	cnt = 0
	for j in range(len(T)):
		if T[j] != S[i + j]:
			cnt += 1
	ans = min(ans, cnt)
print(ans)


S = input()
T = input()
N = len(S)
M = len(T)
ans = set()
for x in range(N - M + 1):
	count = M
	for i in range(M):
		if S[x + i] == T[i]:
			count -= 1
	ans.add(count)
print(min(ans))


S = input()
T = input()
l = len(T)
mx = -1
for i in range(len(S) - l + 1):
	m = [a == b for (a, b) in zip(S[i:i + l], T)].count(True)
	mx = max(m, mx)
print(l - mx)


s = input()
t = input()
ans = 100000
for i in range(len(s) - len(t) + 1):
	score = 0
	U = s[i:i + len(t)]
	for j in range(len(t)):
		if U[j] != t[j]:
			score += 1
	ans = min(ans, score)
print(ans)


s = input()
t = input()
val = 10000
for i in range(len(s) - len(t) + 1):
	cnt = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			cnt += 1
	val = min(val, cnt)
print(val)


(s, t) = (input(), input())
be = len(t)
for i in range(len(s) - len(t) + 1):
	ct = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			ct += 1
	if be > ct:
		be = ct
print(be)


s = input()
t = input()
ans = 10 ** 4
for a in range(len(s) - len(t) + 1):
	tmp = 0
	for b in range(len(t)):
		if s[a + b] == t[b]:
			tmp += 1
	ans = min(ans, len(t) - tmp)
print(ans)


s = input()
t = input()
ans = 10 ** 8
n = len(s)
m = len(t)
for i in range(n - m + 1):
	cnt = 0
	for j in range(m):
		if s[i + j] != t[j]:
			cnt += 1
	ans = min(ans, cnt)
print(ans)


s = input()
t = input()
box = []
for i in range(len(s) - len(t) + 1):
	a = 0
	for j in range(len(t)):
		if t[j] != s[i + j]:
			a += 1
	box.append(a)
print(min(box))


s = input()
t = input()
n = len(s)
m = len(t)
ans = 0
for i in range(n - m + 1):
	c = 0
	for j in range(m):
		if s[i + j] == t[j]:
			c += 1
	ans = max(c, ans)
print(m - ans)


S = input()
T = input()
n = len(S)
m = len(T)
x = int(1000000000.0)
for i in range(n - m + 1):
	cnt = 0
	for j in range(m):
		cnt += S[i + j] != T[j]
	x = min(x, cnt)
print(x)


s = str(input())
t = str(input())
n = len(s)
m = len(t)
ans = m
for i in range(n - m + 1):
	tmp = 0
	for j in range(m):
		if t[j] != s[i + j]:
			tmp += 1
	ans = min(ans, tmp)
print(ans)


(s, t) = open(0).read().split()
(n, m) = (len(s), len(t))
a = 2000
for i in range(n - m + 1):
	b = 0
	for j in range(m):
		b += s[i + j] != t[j]
	a = min(a, b)
print(a)


s = input()
t = input()
ans = 1000
for i in range(0, len(s) - len(t) + 1):
	cnt = 0
	for (m, n) in zip(s[i:i + len(t)], t):
		if m != n:
			cnt += 1
	ans = min(ans, cnt)
print(ans)


S = input()
T = input()
r = 1000
for i in range(len(S) - len(T) + 1):
	r = min(r, sum([S[i + j] != T[j] for j in range(len(T))]))
print(r)


s = input()
t = input()
ans = len(t)
for i in range(len(s) - len(t) + 1):
	w = 0
	for k in range(len(t)):
		if s[i + k] != t[k]:
			w += 1
	ans = min(ans, w)
print(ans)


s = input()
t = input()
n = len(s)
m = len(t)
ma = 10000000000
for i in range(n - m + 1):
	c = 0
	for j in range(m):
		if t[j] != s[i + j]:
			c += 1
	ma = min(c, ma)
print(ma)


def resolve():
	S = input()
	T = input()
	count1 = []
	for i in range(len(S) - len(T) + 1):
		count2 = 0
		for j in range(len(T)):
			if S[i:i + len(T)][j] == T[j]:
				count2 += 1
		count1.append(len(T) - count2)
	print(min(count1))
resolve()


s = input()
t = input()
a = 1000
for i in range(len(s) - len(t) + 1):
	c = 0
	for l in range(len(t)):
		if s[l + i] != t[l]:
			c += 1
	if c < a:
		a = c
print(a)


S = list(input())
T = list(input())
ans = 0
for i in range(len(S)):
	s = S[i:]
	if len(s) < len(T):
		break
	tmp = 0
	for j in range(len(T)):
		if s[j] == T[j]:
			tmp += 1
	ans = max(ans, tmp)
print(len(T) - ans)


(s, t) = (input(), input())
l = len(t)
print(l - max((sum((s[i + j] == t[j] for j in range(l))) for i in range(len(s) - l + 1))))


a = input()
b = input()
c = 1000
for i in range(len(a) - len(b) + 1):
	d = 0
	for j in range(len(b)):
		if a[i + j] != b[j]:
			d += 1
	if d < c:
		c = d
print(c)


S = input()
T = input()
print(min((sum((c != d for (c, d) in zip(S[i:i + len(T)], T))) for i in range(len(S) - len(T) + 1))))


s = input()
t = input()
ans = len(t)
for i in range(0, len(s) - len(t) + 1):
	diff = 0
	for j in range(0, len(t)):
		if t[j] != s[i + j]:
			diff += 1
	ans = min(diff, ans)
print(f'{ans}')


S = input()
T = input()
d = len(S) - len(T)
print(len(T) - max((sum((t == s for (t, s) in zip(T, S[i:i + len(T) + 1]))) for i in range(d + 1))))


S = input()
T = input()
result = len(T)
for s in range(0, len(S) - len(T) + 1):
	diff = 0
	for i in range(0, len(T)):
		if T[i] != S[s + i]:
			diff += 1
	result = min(result, diff)
print(result)


(S, T) = (input(), input())
print(min([sum([0 if x == y else 1 for (x, y) in zip(S[i:i + len(T)], T)]) for i in range(len(S) - len(T) + 1)]))


s = input()
t = input()
score = 1000
for i in range(len(s) - len(t) + 1):
	tmp = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			tmp += 1
	score = min(score, tmp)
print(score)


a = list(input())
b = list(input())
l = []
for i in range(len(a) - len(b) + 1):
	c = 0
	for j in range(len(b)):
		if a[j + i] == b[j]:
			c += 1
	l.append(c)
print(len(b) - max(l))


s = input()
t = input()
ls = len(s)
lt = len(t)
ans = lt
for i in range(0, ls - lt + 1):
	count = 0
	for j in range(lt):
		if s[i + j] != t[j]:
			count += 1
	if count < ans:
		ans = count
print(ans)


S = input()
T = input()
for i in range(len(S) - len(T) + 1):
	tmp = 0
	for j in range(len(T)):
		if S[i + j] != T[j]:
			tmp += 1
	ans = tmp if i == 0 else min(tmp, ans)
print(ans)


s = input()
t = input()
ans = len(t)
for i in range(len(s)):
	if i + len(t) > len(s):
		break
	anss = 0
	for j in range(len(t)):
		if t[j] != s[i + j]:
			anss += 1
	ans = min(ans, anss)
print(ans)


S = input()
T = input()
lenS = len(S)
lenT = len(T)
MIN = float('inf')
for i in range(lenS):
	tmpS = S[i:i + lenT]
	if len(tmpS) != lenT:
		continue
	count = 0
	for i in range(lenT):
		if tmpS[i] != T[i]:
			count += 1
	MIN = min(MIN, count)
print(MIN)


s = input()
t = input()
m = 10000
ct = 0
for i in range(len(s) - len(t) + 1):
	for j in range(len(t)):
		if s[i:i + len(t)][j] != t[j]:
			ct += 1
	m = min(ct, m)
	ct = 0
print(m)


S = input()
T = input()
max_count = 0
for i in range(len(S) - len(T) + 1):
	s = S[i:i + len(T)]
	count = 0
	for j in range(len(T)):
		if s[j] == T[j]:
			count = count + 1
	if max_count <= count:
		max_count = count
		ans = len(T) - count
print(ans)


s = input()
t = input()
ans = float('INF')
for i in range(len(s) - len(t) + 1):
	x = 0
	for j in range(len(t)):
		x += s[i + j] != t[j]
	ans = min(ans, x)
print(ans)


(s, t) = open(0)
print(min((sum((a != b for (a, b) in zip(s[i:-1], t[:-1]))) for i in range(len(s) - len(t) + 1))))


s = list(input())
t = list(input())
r = len(t)
for ii in range(len(s) - len(t) + 1):
	rr = 0
	for jj in range(len(t)):
		if s[ii + jj] != t[jj]:
			rr += 1
	if rr < r:
		r = rr
print(r)


s = input()
t = input()
if t in s:
	print(0)
	return
ns = len(s)
nt = len(t)
ans = nt
k = ns - nt
for i in range(k + 1):
	hoge = s[i:i + nt]
	c = 0
	for j in range(nt):
		if hoge[j] != t[j]:
			c += 1
	ans = min(c, ans)
print(ans)


s = list(input())
t = list(input())
ans = min([sum([0 if s[i + j] == t[j] else 1 for j in range(len(t))]) for i in range(len(s) - len(t) + 1)])
print(ans)


import sys
line_long = sys.stdin.readline().strip()
line_sub = sys.stdin.readline().strip()
len_long = len(line_long)
len_sub = len(line_sub)
min_cnt = len_sub
for idx in range(0, len_long - len_sub + 1):
	this_cnt = 0
	for sub_idx in range(0, len_sub):
		if line_sub[sub_idx] != line_long[sub_idx + idx]:
			this_cnt = this_cnt + 1
	min_cnt = min(min_cnt, this_cnt)
print(min_cnt)


import math
prime = [True for i in range(10 ** 6 + 1)]

def SieveOfEratosthenes(n):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1

def __starting_point():
	s = str(input())
	s1 = str(input())
	c = -10 ** 9
	con = 0
	F = 0
	for i in range(0, len(s)):
		con = 0
		if len(s) - i >= len(s1):
			F = i
			for j in range(0, len(s1)):
				if s[F] == s1[j]:
					con += 1
				F += 1
		c = max(c, con)
	print(len(s1) - c)
__starting_point()


S = input()
T = input()
ans = 100000000
for i in range(len(S) - len(T) + 1):
	ans = min(ans, sum((s != t for (s, t) in zip(T, S[i:i + len(T)]))))
print(ans)


def d(s, t):
	return sum((i != j for (i, j) in zip(s, t)))
(s, t) = (input(), input())
(n, m) = (len(s), len(t))
print(min((d(s[i:i + m], t) for i in range(n - m + 1))))


S = input()
T = input()
ans = len(T)
for s in range(len(S)):
	if len(S) - s < len(T):
		break
	count = 0
	for t in range(len(T)):
		if S[s + t] != T[t]:
			count += 1
	ans = min(count, ans)
print(ans)


s = input()
t = input()
x = len(t)
ans = chk = x
for i in range(len(s) - len(t) + 1):
	chk = x
	for j in range(x):
		chk -= s[i + j] == t[j]
	ans = min(ans, chk)
print(ans)


s = input()
t = input()
tl = len(t)
m = 0
for i in range(len(s) - tl + 1):
	c = 0
	for (x, y) in zip(t, s[i:i + tl]):
		if x == y:
			c += 1
	m = max(m, c)
print(tl - m)


(S, T) = (input(), input())
r = len(T)
for i in range(len(S) - len(T) + 1):
	t = 0
	for j in range(len(T)):
		if S[i + j] != T[j]:
			t += 1
	r = min(r, t)
print(r)


s = input()
t = input()
res = 1000000
for i in range(len(s) - len(t) + 1):
	tmp = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			tmp += 1
	res = min(tmp, res)
print(res)


S = input()
T = input()
count = 0
m = len(T)
l = len(S) - len(T)
for i in range(0, l + 1):
	for j in range(0, len(T)):
		if S[j + i] != T[j]:
			count += 1
	if m > count:
		m = count
	count = 0
print(m)


(S, T) = open(0)
print(min((sum((c != d for (c, d) in zip(S[i:], T[:-1]))) for i in range(len(S) - len(T) + 1))))


S = input()
T = input()

def ans177(S: str, T: str):
	judge_count = 0
	ans_count = 0
	while judge_count <= len(S) - len(T):
		same_count = 0
		for i in range(len(T)):
			if S[judge_count + i] == T[i]:
				same_count += 1
		if same_count >= ans_count:
			ans_count = same_count
		judge_count += 1
	return len(T) - ans_count
print(ans177(S, T))


S = input()
T = input()
ans = 10 ** 9
for i in range(len(S) - len(T) + 1):
	tmp = 0
	for j in range(len(T)):
		if S[i + j] != T[j]:
			tmp += 1
	ans = min(tmp, ans)
print(ans)


S = input()
T = input()
ma = 0
match = 0
for i in range(len(S) - len(T) + 1):
	match = 0
	for j in range(len(T)):
		if S[i + j] == T[j]:
			match += 1
	ma = max(ma, match)
print(len(T) - ma)


S = input()
T = input()
ans = 1000000
for i in range(len(S) - len(T) + 1):
	cnt = len(T)
	for j in range(len(T)):
		if S[i + j] == T[j]:
			cnt -= 1
	ans = min(cnt, ans)
print(ans)


s = input()
t = input()
x = len(s)
y = len(t)
ans = 10000
for i in range(x):
	if i > x - y:
		break
	tm = 0
	for j in range(0, y):
		if s[i + j] != t[j]:
			tm += 1
	ans = min(tm, ans)
print(ans)


s = input()
t = input()
mn = len(s)
for i in range(len(s) - len(t) + 1):
	cnt = 0
	for (x, y) in zip(t, s[i:i + len(t)]):
		if x != y:
			cnt += 1
	mn = min(cnt, mn)
print(mn)


s = input()
t = input()
m = 1000
for i in range(len(s) - len(t) + 1):
	mm = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			mm += 1
	m = min(mm, m)
print(m)


a = input()
b = input()
c = len(a) - len(b)
d = []
for i in range(len(a) - len(b) + 1):
	a[i:i + len(b)]
	count = 0
	for j in range(len(b)):
		if a[i:i + len(b)][j] == b[j]:
			count += 1
	d.append(len(b) - count)
print(min(d))


ans = 10 ** 5
s = input()
t = input()
for i in range(len(s) - len(t) + 1):
	tmp = 0
	for j in range(len(t)):
		tmp += s[i + j] == t[j]
	ans = min(ans, len(t) - tmp)
print(ans)


(s, t) = (input(), input())
ls = len(s)
lt = len(t)
ans = 1000000000000
for i in range(ls - lt + 1):
	ans_sub = 0
	for j in range(lt):
		if t[j] != s[i + j]:
			ans_sub += 1
	ans = min(ans, ans_sub)
print(ans)


s = input()
t = input()
n = len(s) - len(t) + 1
ans = 1001001001
for i in range(n):
	ans = min(ans, sum((j != k for (j, k) in zip(s[i:i + len(t)], t))))
print(ans)


s = input()
t = input()
ans = 0
for i in range(len(s) - len(t) + 1):
	tm = 0
	for j in range(len(t)):
		if s[i + j] == t[j]:
			tm += 1
	ans = max(tm, ans)
print(len(t) - ans)


s = input()
t = input()
L = len(s)
l = len(t)
X = []
for i in range(L - l + 1):
	x = 0
	for j in range(l):
		if s[i + j] != t[j]:
			x += 1
	X.append(x)
print(min(X))


S = input()
T = input()
st = [0] * (len(S) - len(T) + 1)
for i in range(len(S) - len(T) + 1):
	for (j, t) in enumerate(T):
		st[i] += S[i + j] == t
print(len(T) - max(st))


S = input()
T = input()
l = len(S) - len(T) + 1
ans = len(T)
t = len(T)
for i in range(l):
	s = S[i:i + t]
	ans = min(ans, len([0 for i in range(t) if T[i] != s[i]]))
print(ans)


s = input()
t = input()
mn = 1001
for i in range(len(s) - len(t) + 1):
	sm = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			sm += 1
	if sm < mn:
		mn = sm
print(mn)


(s, t) = open(0)
print(min((sum((x != y for (x, y) in zip(s[i:], t[:-1]))) for i in range(len(s) - len(t) + 1))))


def main():
	S = input()
	T = input()
	size = len(T)
	count = 10000
	for i in range(len(S) - size + 1):
		x = 0
		for j in range(size):
			if S[i + j] != T[j]:
				x += 1
		count = min(count, x)
	print(count)

def __starting_point():
	main()
__starting_point()


s = input()
t = input()
tlen = len(t)
print(min((sum((1 for (a, b) in zip(s[i:i + tlen], t) if a != b)) for i in range(0, len(s) - len(t) + 1))))


s = input()
t = input()
l = len(s)
l2 = len(t)
ans = 1000000
for i in range(l - l2 + 1):
	curr = 0
	for j in range(i, i + l2):
		if s[j] != t[j - i]:
			curr += 1
	if curr < ans:
		ans = curr
print(ans)


s = input()
t = input()
s_len = len(s)
t_len = len(t)
counter = 0
count_max = 0
for i in range(s_len - t_len + 1):
	for j in range(t_len):
		if s[i + j] == t[j]:
			counter += 1
			if counter > count_max:
				count_max = counter
	counter = 0
print(t_len - count_max)


s = input()
t = input()
ans = 9999999999999999
for i in range(len(s) - len(t) + 1):
	res = 0
	for j in range(i, i + len(t)):
		res += s[j] != t[j - i]
	ans = min(ans, res)
print(ans)


(s, t) = (input(), input())
ans = len(t)
for i in range(len(s) - len(t) + 1):
	s2 = s[i:i + len(t)]
	c = 0
	for j in range(len(s2)):
		if s2[j] != t[j]:
			c += 1
	ans = min(ans, c)
print(ans)


s = input()
t = input()
a = 0
for i in range(len(s) - len(t) + 1):
	c = 0
	for (j, d) in enumerate(t):
		if s[i + j] == d:
			c += 1
	a = max(a, c)
print(len(t) - a)


S = input()
T = input()
(s, t) = (len(S), len(T))
ans = t
for i in range(s - t + 1):
	d = 0
	u = S[i:i + t]
	for j in range(t):
		if u[j] != T[j]:
			d += 1
	ans = min(ans, d)
print(ans)


s = input()
t = input()
lt = len(t)
x = lt
for i in range(len(s) - lt + 1):
	a = 0
	for j in range(lt):
		if s[i + j] != t[j]:
			a += 1
	x = min(x, a)
print(x)


S = input()
T = input()
n = len(S)
m = len(T)
ans = n
for i in range(n - m + 1):
	cnt = 0
	for j in range(m):
		if S[i + j] != T[j]:
			cnt += 1
	ans = min(ans, cnt)
print(ans)


s = input()
t = input()
ans = 10 ** 10
S = len(s)
T = len(t)
for i in range(S - T + 1):
	chk = 0
	for j in range(T):
		if s[i + j] != t[j]:
			chk += 1
	ans = min(chk, ans)
print(ans)


def answer(s: str, t: str) -> int:
	result = len(t)
	for i in range(len(s) - len(t) + 1):
		count = 0
		for j in range(len(t)):
			if t[j] != s[i + j]:
				count += 1
		result = min(result, count)
	return result

def main():
	s = input()
	t = input()
	print(answer(s, t))

def __starting_point():
	main()
__starting_point()


s = input()
t = input()
ans = len(t)
for i in range(len(s) - len(t) + 1):
	ans = min(ans, sum((si != ti for (si, ti) in zip(s[i:], t))))
print(ans)


s = input()
t = input()
ls = len(s)
lt = len(t)
ans = 0
for i in range(ls - lt + 1):
	k = 0
	for j in range(lt):
		if s[i + j] == t[j]:
			k += 1
	ans = max(ans, k)
print(lt - ans)


S = input()
T = input()
A = len(S)
B = len(T)
M = 10 ** 10
for i in range(A - B + 1):
	K = 0
	for k in range(B):
		K += S[i + k] != T[k]
	M = min(M, K)
print(M)


s = list(input())
t = list(input())
d = 0
for a in range(len(s) - len(t) + 1):
	c = 0
	for b in range(len(t)):
		if s[a + b] == t[b]:
			c = c + 1
	if c > d:
		d = c
print(len(t) - d)


s = input()
t = input()
q = 10 ** 18
for i in range(len(s) - len(t) + 1):
	ans = 0
	for j in range(len(t)):
		if t[j] != s[i + j]:
			ans += 1
	q = min(ans, q)
print(q)


(s, t) = (input(), input())
print(min((sum((c != d for (c, d) in zip(s[i:], t))) for i in range(len(s) - len(t) + 1))))


S = input()
T = input()
n = len(S)
m = len(T)
ans = n + 10
for i in range(n - m + 1):
	x = 0
	for j in range(m):
		x += S[i + j] != T[j]
	ans = min(ans, x)
print(ans)


S = input()
T = input()
L = len(S) - len(T)
b = 0
if L > 0:
	a = [0] * L
	for i in range(L):
		for j in range(len(T)):
			if S[j + i] == T[j]:
				a[i] = a[i] + 1
	A = sorted(a, reverse=True)
	print(len(T) - A[0])
if L == 0:
	for l in range(len(S)):
		if S[l] == T[l]:
			b = b + 1
	print(len(T) - b)


import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp
INF = inf
MOD = 1000000007
s = input()
t = input()
tmp = 0
res = 0
res = INF
ls = len(s)
lt = len(t)
for i in range(ls - lt + 1):
	tmp = 0
	for j in range(lt):
		if t[j] != s[i + j]:
			tmp += 1
	res = min(res, tmp)
print(res)


MOD = 10 ** 9 + 7
S = input()
T = input()
ans = len(T)
for i in range(len(S) - len(T) + 1):
	match = 0
	for j in range(len(T)):
		if T[j] == S[i + j]:
			match += 1
	ans = min(ans, len(T) - match)
print(ans)


s = input()
t = input()
c = len(t)
for i in range(len(s) - len(t) + 1):
	d = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			d += 1
	if d < c:
		c = d
print(c)


s = input()
t = input()
track = len(t)
for i in range(len(s) - len(t) + 1):
	x = 0
	for k in range(len(t)):
		if t[k] != s[i + k]:
			x += 1
	track = min(track, x)
print(track)


S = input()
T = input()
res = 0
for i in range(len(S) - len(T) + 1):
	a = 0
	for j in range(len(T)):
		a += S[i + j] == T[j]
	res = max(res, a)
print(len(T) - res)


S = input()
T = input()
Z = 0
K = []
for i in range(len(S) - len(T) + 1):
	for j in range(len(T)):
		if S[j + i] != T[j]:
			Z += 1
	K.append(Z)
	Z = 0
print(min(K))


S = input()
T = input()
ans = 100000
for i in range(len(S) - len(T) + 1):
	score = 0
	U = S[i:i + len(T)]
	for j in range(len(T)):
		if U[j] != T[j]:
			score += 1
	ans = min(ans, score)
print(ans)


s = input()
t = input()

def count(x, y):
	return sum((xi != yi for (xi, yi) in zip(x, y)))
ans = min((count(s[i:i + len(t)], t) for i in range(len(s) - len(t) + 1)))
print(ans)


s = input()
t = input()
lt = len(t)
ls = len(s)
a = []
for i in range(ls - lt + 1):
	m = 0
	for j in range(lt):
		if t[j] != s[i + j]:
			m += 1
	a.append(m)
print(min(a))


S = input()
T = input()
c = len(T)
for i in range(len(S) - len(T) + 1):
	d = 0
	for j in range(len(T)):
		if S[i + j] != T[j]:
			d += 1
	if d < c:
		c = d
print(c)


S = input()
T = input()
ans = len(T)
for i in range(len(S) - len(T) + 1):
	ans = min(ans, sum([x[0] != x[1] for x in zip(T, S[i:])]))
print(ans)


S = input()
T = input()
count_list = []
count = 0
for i in range(len(S) - len(T) + 1):
	for j in range(len(T)):
		if T[j] == S[j + i]:
			count += 1
	count_list.append(count)
	count = 0
ans = len(T) - max(count_list)
print(ans)


s = list(input())
t = list(input())
ans = []
for i in range(len(s) - len(t) + 1):
	ct = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			ct += 1
	ans.append(ct)
print(min(ans))


S = input()
T = input()
A = []
for n in range(len(S) - len(T) + 1):
	count = 0
	for (s, t) in zip(S[n:n + len(T)], T):
		if s != t:
			count += 1
	A += [count]
print(min(A))


S = list(input())
T = list(input())
NS = len(S)
NT = len(T)
X = [0] * (NS - NT + 1)
for i in range(NS - NT + 1):
	for ii in range(NT):
		if S[i + ii] == T[ii]:
			X[i] += 1
print(NT - max(X))


S = input()
T = input()
M = len(S)
N = len(T)
ans = 1000
for i in range(M - N + 1):
	temp = 0
	for j in range(N):
		if T[j] == S[i + j]:
			temp += 1
	ans = min(ans, N - temp)
print(ans)


def compare(s1, t1):
	count = 0
	for (a, b) in zip(s1, t1):
		if a != b:
			count += 1
	return count
s = input()
t = input()
ans = 1001
for i in range(len(s) - len(t) + 1):
	ret = compare(s[i:], t)
	ans = min(ret, ans)
print(ans)


import sys
input = sys.stdin.readline
s = str(input()).replace('\n', '')
t = str(input()).replace('\n', '')
ans = len(t)
for i in range(len(s) - len(t) + 1):
	diff = 0
	for j in range(len(t)):
		if t[j] != s[i + j]:
			diff += 1
	if ans > diff:
		ans = diff
print(ans)


s = input()
t = input()
ans = 10000
for i in range(len(s) - len(t) + 1):
	score = 0
	u = s[i:i + len(t)]
	for j in range(len(t)):
		if u[j] != t[j]:
			score += 1
	ans = min(ans, score)
print(ans)


s = input()
t = input()
a = len(s)
b = len(t)
ans = 2000
for i in range(a - b + 1):
	k = 0
	for j in range(b):
		if s[i + j] != t[j]:
			k += 1
	ans = min(ans, k)
print(ans)


s = list(input())
t = list(input())
ans = 10 ** 7
for i in range(len(s) - len(t) + 1):
	c = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			c = c + 1
	if c < ans:
		ans = c
print(ans)


S = input()
T = input()
n = 0
for i in range(len(S) - len(T) + 1):
	tmp = 0
	for j in range(len(T)):
		if S[i + j] == T[j]:
			tmp += 1
	n = max(tmp, n)
print(len(T) - n)


(s, t) = (input(), input())
mn = 1000
for i in range(len(s) - len(t) + 1):
	curr = 0
	for j in range(len(t)):
		curr += t[j] != s[i + j]
	mn = min(mn, curr)
print(mn)


S = input()
T = input()
a = len(T)
for i in range(len(S) - len(T) + 1):
	c = 0
	for (j, t) in enumerate(T):
		if S[i + j] != t:
			c += 1
	a = min(a, c)
print(a)


S = input()
T = input()
m = 0
for i in range(len(S) - len(T) + 1):
	n = 0
	for j in range(len(T)):
		if S[i + j] == T[j]:
			n += 1
	if n > m:
		m = n
print(len(T) - m)


(t, s) = (input(), input())
ans = 100000000000000000000000000
for j in range(0, len(t) - len(s) + 1):
	ans = min(ans, sum((1 for i in range(len(s)) if s[i] != t[i + j])))
print(ans)


import itertools

def main():
	ans = 0
	ans1 = []
	s = input()
	t = input()
	ss = len(s)
	ts = len(t)
	for i in range(ss - ts + 1):
		for (j, x) in enumerate(s[0 + i:ts + i]):
			if t[j] == x:
				ans += 1
		ans1.append(ans)
		ans = 0
	print(ts - max(ans1))

def __starting_point():
	main()
__starting_point()


s = input()
t = input()
ans = 10 ** 7
for i in range(len(s) - len(t) + 1):
	ansi = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			ansi += 1
	ans = min(ans, ansi)
print(ans)


A = str(input())
B = str(input())
C = [0] * len(A)
for i in range(len(A) - len(B) + 1):
	for j in range(len(B)):
		if A[i + j] == B[j]:
			C[i] += 1
print(len(B) - max(C))


S = input()
T = input()
t = 0
s = 0
a = 0
while a <= len(S) - len(T):
	u = S[a:a + len(T)]
	for j in range(len(T)):
		if u[j] == T[j]:
			t = t + 1
	if s < t:
		s = t
	t = 0
	a = a + 1
print(len(T) - s)


s = list(input())
t = list(input())
ans = 10 ** 3 + 1
for i in range(len(s) - len(t) + 1):
	count = 0
	for j in range(len(t)):
		if s[i + j] != t[j]:
			count += 1
	ans = min(count, ans)
print(ans)


S = input()
T = input()
num = [0] * len(S)
for i in range(len(S) - len(T) + 1):
	for t in range(len(T)):
		if S[i + t] == T[t]:
			num[i] += 1
print(len(T) - max(num))


S = input()
T = input()
U = [0] * (len(S) - len(T) + 1)
for j in range(len(S) - len(T) + 1):
	for i in range(len(T)):
		if S[i + j] != T[i]:
			U[j] += 1
print(min(U))


s = input()
t = input()
S = len(s)
T = len(t)
ans = 100000
for i in range(S - T + 1):
	x = 0
	for j in range(T):
		if s[i + j] != t[j]:
			x += 1
	ans = min(ans, x)
print(ans)


S = input()
T = input()
len_T = len(T)
m = max((sum([1 for (s, t) in zip(S[i:i + len_T], T) if s == t]) for i in range(len(S) - len_T + 1)))
print(len_T - m)


S = list(input())
T = list(input())
cnt = 0
for i in range(len(S) - len(T) + 1):
	a = 0
	for j in range(len(T)):
		if S[i + j] == T[j]:
			a += 1
	cnt = max(a, cnt)
print(len(T) - cnt)


s = input()
t = input()
ans = len(t)
for i in range(len(s) - len(t) + 1):
	cnt = len(t)
	for j in range(len(t)):
		if s[i + j] == t[j]:
			cnt -= 1
	if cnt < ans:
		ans = cnt
print(ans)


s = input()
t = input()
k = 0
for i in range(len(s) - len(t) + 1):
	a = s[i:len(t) + i]
	kari = 0
	for j in range(len(t)):
		if a[j] == t[j]:
			kari += 1
	k = max(kari, k)
print(len(t) - k)


(S, T) = (input(), input())
best = len(T)
for i in range(len(S) - len(T) + 1):
	best = min(best, sum((S[i + j] != c for (j, c) in enumerate(T))))
print(best)


S = input()
T = input()
answer = len(S)

def calculate_difference(word_s, word_t):
	return sum([0 if word_s[i] == word_t[i] else 1 for i in range(len(word_s))])
for s_index in range(0, len(S) - len(T) + 1):
	s_substring = S[s_index:s_index + len(T)]
	answer = min(answer, calculate_difference(s_substring, T))
print(answer)


s = input()
t = input()
sl = len(s)
tl = len(t)
ans = 10 ** 9
for i in range(sl - tl + 1):
	cnt = 0
	for j in range(tl):
		if s[i + j] != t[j]:
			cnt += 1
	ans = min(ans, cnt)
print(ans)


s = input()
t = input()
n = len(s)
k = len(t)
c = n
for i in range(n - k + 1):
	c1 = 0
	for j in range(i, i + k):
		if s[j] != t[j - i]:
			c1 += 1
	c = min(c, c1)
print(c)


S = input()
T = input()
N = len(S)
M = len(T)
i = 0
ans = 10 ** 9
while i + M <= N:
	ans = min(ans, sum((s != t for (s, t) in zip(S[i:i + M], T))))
	i += 1
print(ans)


s = input()
t = input()
sn = len(s)
tn = len(t)
ans = float('INF')
for i in range(sn - tn + 1):
	cnt = 0
	for j in range(tn):
		if s[i + j] != t[j]:
			cnt += 1
	ans = min(ans, cnt)
print(ans)


l1 = input()
l2 = input()
n_steps = []
for i in range(len(l1) - len(l2) + 1):
	num = 0
	for (i, l) in enumerate(l2):
		if l1[i] != l:
			num += 1
	n_steps.append(num)
	l1 = l1[1:]
n_steps.sort()
print(n_steps[0])


s = input()
t = input()
n = len(t)
out = 2000
for i in range(len(s) - n + 1):
	p = s[i:i + n]
	count = 0
	for j in range(n):
		if t[j] != p[j]:
			count += 1
	if count < out:
		out = count
print(out)


s = input()
t = input()
m = len(s)
n = len(t)
ans = 1000
for i in range(m - n + 1):
	k = 0
	for j in range(n):
		k += s[i + j] != t[j]
	ans = min(ans, k)
print(ans)


import numpy as np

def __starting_point():
	s = input()
	t = input()
	min_diff = 9999
	len_s = len(s)
	len_t = len(t)
	for i in range(len_s - len_t + 1):
		count = 0
		for j in range(len_t):
			if t[j] is not s[i + j]:
				count += 1
		min_diff = min(count, min_diff)
	print(min_diff)
__starting_point()


s = input()
t = input()
ans_list = []
for i in range(len(s) - len(t) + 1):
	u = s[i:len(t) + i]
	check_count = 0
	for (a, b) in zip(u, t):
		if a != b:
			check_count += 1
	ans_list.append(check_count)
print(min(ans_list))


s = input()
t = input()
(n, m) = (len(s), len(t))
print(min((sum((si != ti for (si, ti) in zip(s[i:i + m], t))) for i in range(n - m + 1))))


S = input()
T = input()
ans = len(T) + 1
for i in range(len(S) - len(T) + 1):
	val = sum((1 for (a, b) in zip(S[i:i + len(T)], T) if a != b))
	ans = min(ans, val)
print(ans)


S = input()
T = input()
n = len(S) - len(T) + 1
min = 1000
if T in S:
	print(0)
else:
	for i in range(n):
		tmp = 0
		for j in range(len(T)):
			if S[i + j] != T[j]:
				tmp += 1
		if tmp < min:
			min = tmp
	print(min)


def main():
	S = input()
	T = input()
	min = len(T)
	for i in range(len(S) - len(T) + 1):
		cnt = 0
		desS = S[i:i + len(T)]
		for j in range(len(T)):
			if desS[j] == T[j]:
				cnt += 1
		if min > len(T) - cnt:
			min = len(T) - cnt
	print(min)

def __starting_point():
	main()
__starting_point()


S = input()
T = input()
N = len(S)
n = len(T)
ans = n
for i in range(N - n + 1):
	ans = min(ans, sum((S[i + j] != T[j] for j in range(n))))
print(ans)


a = [str(input()) for i in range(2)]
S = a[0]
T = a[1]
length_S = len(S)
length_T = len(T)
l_S = [str(x) for x in list(str(S))]
l_T = [str(y) for y in list(str(T))]
l_s = []
for i in range(length_S - length_T + 1):
	s = l_S[i:i + length_T]
	l_s.append(s)
l_b = []
for j in range(length_S - length_T + 1):
	l_a = []
	num1 = 0
	for i in range(length_T):
		if l_T[i] != l_s[j][i]:
			num1 += 1
		l_a.append(num1)
	l_b.append(l_a)
l_c = []
for i in range(length_S - length_T + 1):
	num2 = l_b[i][-1]
	l_c.append(num2)
ans = min(l_c)
print(ans)


s = input()
t = input()
len_s = len(s)
len_t = len(t)
ini = 0
l_cnt = []
for i in range(len_s - len_t + 1):
	cut = s[i:i + len_t]
	cnt = 0
	for (i, w) in enumerate(t):
		if w != cut[i]:
			cnt += 1
	l_cnt.append(cnt)
print(min(l_cnt))


s = input()
t = input()
ans = 10000
for i in range(len(s) - len(t) + 1):
	tmp = 0
	for j in range(len(t)):
		if t[j] != s[i + j]:
			tmp += 1
	ans = min(ans, tmp)
print(ans)


s = input()
t = input()
n = len(s)
m = len(t)
(a, x) = (m, m)
for i in range(n - m + 1):
	x = m
	for j in range(m):
		x -= s[i + j] == t[j]
	a = min(a, x)
print(a)


(s, t) = (input(), input())
len_t = len(t)
dif = 1001
for i in range(len(s) - len_t + 1):
	dif = min(dif, sum([x != y for (x, y) in zip(s[i:i + len_t], t)]))
print(dif)


S = input().strip()
T = input().strip()
l = len(T)

def diff(s):
	return sum([s[i] != T[i] for i in range(l)])
print(min([diff(S[i:i + l]) for i in range(len(S) - l + 1)]))


S = input()
T = input()
A = []
for i in range(len(S) - len(T) + 1):
	s = S[i:i + len(T)]
	t = [T[j] for j in range(len(T)) if s[j] != T[j]]
	A.append(len(t))
print(min(A))


s = input()
t = input()
mx_match = 0
for i in range(len(s) - len(t) + 1):
	mx_match = max(mx_match, sum((s[i + j] == t[j] for j in range(len(t)))))
print(len(t) - mx_match)


S = input()
T = input()
len_T = len(T)
ans_min_change_word = len_T
for i in range(len(S) - len_T + 1):
	tmp_change_word = 0
	for j in range(len_T):
		if S[i + j] != T[j]:
			tmp_change_word += 1
	ans_min_change_word = min(ans_min_change_word, tmp_change_word)
print(ans_min_change_word)


s = list(input())
t = list(input())
r = tn = len(t)
for u in (s[i:i + tn] for i in range(len(s) - tn + 1)):
	k = 0
	for (i, j) in zip(u, t):
		k += i != j
	r = min(r, k)
print(r)


S = input()
T = input()
counts = []
for i in range(len(S) - len(T) + 1):
	count = len([s for (s, t) in zip(S[i:], T) if s != t])
	counts.append(count)
print(min(counts))


def b177(s, t):
	ans = 10 ** 8
	for i in range(len(s) - len(t) + 1):
		count = 0
		for w in range(len(t)):
			if s[i + w] == t[w]:
				count += 1
		ans = min(ans, len(t) - count)
	return ans

def main():
	s = list(str(input()))
	t = list(str(input()))
	print(b177(s, t))

def __starting_point():
	main()
__starting_point()


(S, T) = open(0).read().split()
score = 0
for i in range(len(S) - len(T) + 1):
	score = max(score, sum([T[k] == S[i + k] for k in range(len(T))]))
print(len(T) - score)


a = input()
b = input()
ans = 10 ** 10
for i in range(len(a) - len(b) + 1):
	cnt = 0
	for j in range(len(b)):
		if a[i + j] != b[j]:
			cnt += 1
	ans = min(ans, cnt)
print(ans)


a = input()
b = input()
m = len(a)
n = len(b)
ans = 10000000000.0 + 7
for i in range(m - n + 1):
	c = 0
	for j in range(n):
		if a[i + j] != b[j]:
			c += 1
	ans = min(c, ans)
print(ans)


s = input()
t = input()
l = []
for i in range(len(s) - len(t) + 1):
	cha = 0
	for j in range(len(t)):
		if s[j + i] == t[j]:
			cha += 1
	l.append(cha)
print(len(t) - max(l))


import sys
readline = sys.stdin.readline
S = readline().rstrip()
T = readline().rstrip()
ans = 10 ** 10
for s_ind in range(len(S)):
	if s_ind + len(T) > len(S):
		break
	change = 0
	for t_ind in range(len(T)):
		if T[t_ind] != S[s_ind + t_ind]:
			change += 1
			if change > ans:
				break
	if ans > change:
		ans = change
print(ans)


s = input()
t = input()
l = 0
p = 0
for i in range(len(s) - len(t) + 1):
	for j in range(len(t)):
		if t[j] == s[j + i]:
			p += 1
	l = max(l, p)
	p = 0
print(len(t) - l)


s = input()
t = input()
if t in s:
	print(0)
	return
r = 0
for i in range(0, len(s) - len(t) + 1):
	sub_str = s[i:i + len(t)]
	c = 0
	for (a, b) in zip(sub_str, t):
		if a == b:
			c += 1
	r = max(r, c)
	if r == len(t) - 1:
		break
print(len(t) - r)


(s, t) = open(0).read().split()
res = len(t)
for i in range(len(s) - len(t) + 1):
	cnt = 0
	for j in range(len(t)):
		if s[i + j] == t[j]:
			cnt += 1
	res = min(len(t) - cnt, res)
print(res)


S = input()
T = input()
l = len(T)
for i in range(len(S) - len(T) + 1):
	n = 0
	for k in range(len(T)):
		if S[i + k] != T[k]:
			n += 1
	l = min(l, n)
print(l)


s = input()
t = input()
u = m = len(t)
for i in range(len(s) - u + 1):
	m = min(m, sum([1 for j in range(u) if s[i + j] != t[j]]))
print(m)


S = input()
T = input()

def d(s, t):
	return sum([1 if i != j else 0 for (i, j) in zip(s, t)])
print(min([d(S[i:], T) for i in range(len(S) - len(T) + 1)]))