Problem:
 Score : 200 points    Problem Statement 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 1 cabacc
abc      Sample Output 1 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.       Sample Input 2 codeforces
atcoder      Sample Output 2 6

Solution (Python):
S = input() 
T = input() 

min_hamming = len(T)
for i in range(len(S) - len(T) + 1) :
    
    hamming = 0
    for ch1, ch2 in zip(S[i:i+len(T)], T):
        hamming += 1 if ch1 != ch2 else 0
    
    min_hamming = min(min_hamming, hamming)

print(min_hamming)

Solution (Python):
s1 = input()
s2 = input()
list_s1 = list(s1)
list_s2 = list(s2)
len_s1 = len(s1)
len_s2 = len(s2)
change_count_min = len_s2
for i in range(len_s1 - len_s2 + 1):
    change_count = len_s2
    for j in range(len_s2):
        if list_s1[j+i] == list_s2[j]:
            change_count -= 1
    if change_count < change_count_min:
        change_count_min = change_count
print(change_count_min)

Solution (Python):


S=input()
T=input()

Ss=[]
Ts=[]
Us=[]
Vs=[]

len_T=len(T)
len_S=len(S)

s=0


for t in range(len_T):
    Ts.append(T[t])
    Ss.append(S[t])


for t in range(len_T):
    Us.append(Ts[t]!=Ss[t])
Vs.append(sum(Us))


for s in range(1,len_S-len_T+1):
    
    Ss.append(S[len_T+s-1])
    Ss.remove(S[s-1])
    
    Us=[]
    for t in range(len(T)):
        Us.append(Ts[t]!=Ss[t])
    Vs.append(sum(Us))
    
print(str(min(Vs)))

Solution (Python):
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)

Solution (Python):
s = input()
t = input()
 
ans = 0
 
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
 
  if ans <= count:
    ans = count
print(len(t) - ans)

Solution (Python):
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt
from copy import deepcopy
 
def main():
    s = input()
    t = input()

    min_num = 10**5
    max_num = 0
    count = 0
    for i in range(len(s) - len(t)+1):
        for j in range(len(t)):
            if s[i+j] == t[j]:
                count += 1
        if max_num <= count:
            max_num = count
        count = 0

    print(len(t) - max_num)

if __name__ == "__main__":
    main()

Solution (Python):
S=input()
T=input()
a=0
for i in range(0,len(S)-len(T)+1):
    count=0
    for j in range(0,len(T)):
        if S[i+j]==T[j]:
            count+=1
    if a<=count:
        a=count
print(len(T)-a)

Solution (Python):
S = input()
T = input()

min_m = len(T)
dif = range(len(S)-min_m+1)

for j in dif:
  St = S[j:len(T)+j]
  miss = 0
  for i in range(len(T)):
    if St[i] != T[i]:
      miss += 1
  if miss < min_m:
    min_m = miss

print(min_m)

Solution (Python):
s = input()
t = input()

ans = 10**10

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(ans, tmp)
  
print(ans)

Solution (Python):


S = input()
T = input()

X = []
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
    X.append(c)
print(len(T) - max(X))

Solution (Python):
def main():
    s, t = input(), input()
    ans = len(t)
    for i in range(len(s) - len(t)+1):
        substr = s[i:i+len(t)]
        diff = 0
        for a, b in zip(substr, t):
            if a != b:
                diff += 1
        if ans > diff:
            ans = diff
    print(ans)

if __name__=="__main__":
    main()

Solution (Python):
s=str(input())
s1=str(input())
l=[]
for i in range(0,len(s)-len(s1)+1):
    e=s[i:i+len(s1)]
    f=0
    for j in range(0,len(e)):
        if(e[j]!=s1[j]):
            f=f+1
    l.append(f)
print(min(l))

Solution (Python):
s=input()
t=input()

ans=10*100

for i in range(len(s)):
  ss=len(t)+i
  a=s[i:ss]
  if len(t) != len(a):
    continue
  aaa=0
  for j in range(len(t)):
    if t[j] != a[j]:
      aaa+=1
  ans=min(ans,aaa)
print(ans)

Solution (Python):
S = input()
T = input()
count = []
for k in range(0,len(S)-len(T)+1):
    sum = 0
    for i in range(k,k+len(T)):
        if (S[i] != T[i-k]):
            sum += 1
    count.append(sum)

print(min(count))

Solution (Python):
S = input()
T = input()
 
ans = 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
    ans = min(ans, tmp)
print(ans)

Solution (Python):
S = input().rstrip()
T = input().rstrip()

ans = 1000
for offset in range(len(S) - len(T) + 1):
    miss = 0
    for s, t in zip(S[offset:offset+len(T)], T):
        if s != t:
            miss += 1
    ans = min(ans, miss)

print(ans)

Solution (Python):
S = input()
T = input()
n = len(T)
ans = len(T)
for st in range(0, len(S)-len(T)+1):
    SS = S[st:st+len(T)]
    tmp = len(T)
    for s,t in zip(SS,T):
        if s==t:
            tmp -= 1
    ans = min(ans, tmp)
print(ans)

Solution (Python):
s = input()
t = input()

ans = 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
    ans = min(ans, cnt)
print(ans)

Solution (Python):
S = input()
T = input()

S_len = len(S)
T_len = len(T)
A_sum = []
count = 0

for i in range(S_len - T_len + 1):
    for j in range(T_len):
        if S[i+j] == T[j]:
            count += 1
    A_sum.append(count)
    count = 0

ans = T_len - max(A_sum) 

print(ans)

Solution (Python):




INF = 10**9

s = input()
t = input()
ans = INF
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)

Solution (Python):
S = input()
T = input()

s = len(S)
t = len(T)

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

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

Solution (Python):
import sys
from collections import defaultdict as dd
from collections import deque
from functools import *
from fractions import Fraction as f
from copy import *
from bisect import *	
from heapq import *
from math import *
from itertools import permutations ,product
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 

if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def inc(d,c):
	d[c]=d[c]+1 if c in d else 1
def bo(i):
	return ord(i)-ord('A')	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def comp(a,b):
	if(a>b):
		return 2
	return 2 if a==b else 0		
def gi():	
	return [xx for xx in input().split()]
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j):
	return 0<=i<n and 0<=j<n	
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)


tt=1

while tt>0:
	tt-=1
	s=si()
	t=si()
	n=len(s)
	m=len(t)
	i=m-1
	mini=n	
	while i<n:
		c=0
		for j in range(0,m):
				if s[i-m+1+j]!=t[j]:
					c+=1
		mini=min(mini,c)
		i+=1		
	print(mini)

Solution (Python):
S, T = input(), input()

ret = len(T)



for st in range(0, len(S)-len(T) + 1):

    diff = 0

    for idx in range(0, len(T)):
        if S[st + idx] != T[idx]:
            diff += 1

    ret = min(ret, diff)

print('{}'.format(ret))

Solution (Python):
import sys

def main():
    
    

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

    
    print(len(p)-cnt)

if __name__ == '__main__':
    main()

Solution (Python):





s = input()
t = input()
ans = len(t)

for i in range(len(s) - len(t) + 1):
    dif = 0
    for j in range(len(t)):
        if t[j] != s[i + j]:
            dif = dif + 1

    ans = min(ans, dif)
print(ans)

Solution (Python):
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)

Solution (Python):
S= input()
T=input()
mi = 3000
for i in range(0,len(S)-len(T)+1):
    c = 0
    for j in range(0,len(T)):
        
        
        if S[i+j] != T[j]:
            c += 1

        
    if mi > c:
        mi = c
print(mi)

Solution (Python):
s = input()
t = input()
ans = len(t)

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

Solution (Python):
s = input()
t = input()
n = len(s)
m = len(t)
ans = 2000
for i in range(n):
  if i+m > n:
    break
  u = s[i:i+m]
  cnt = 0
  for j in range(m):
    if t[j] != u[j]:
      cnt += 1
  ans = min(ans, cnt)
print(ans)

Solution (Python):
from sys import stdin
input = stdin.readline

def Judge(S, T):
    ls = len(S)
    lt = len(T)
    m = 0
    for i in range(ls-lt+1):
        tmp = 0
        for j in range(lt):
            if S[i+j] == T[j]:
                tmp += 1
        if m < tmp:
            m = tmp
    return lt - m

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

print(Judge(S, T))

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

Solution (Python):
S = input()
s = len(S)
T = input()
t = len(T)

cnt = t
for i in range(s-t+1):
    dif = 0
    for j in range(t):
        if S[i+j] != T[j]:
            dif += 1
    if cnt > dif:
        cnt = dif
print(cnt)

Solution (Python):
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)

Solution (Python):
def compare(t,s):
  diff=0
  assert len(t) == len(s)
  for i in range(len(s)):
    if s[i]!=t[i]:
      diff+=1
  return diff
 
t = input().strip()
s = input().strip()
smallchange = len(s)
assert len(t) >= len(s)
for i in range(len(t)-len(s)+1):
  x = compare(t[i:len(s)+i], s)
  if smallchange > x:
    smallchange = x
 
print(smallchange)

Solution (Python):
s = input().strip()
t = input().strip()

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

Solution (Python):
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)

Solution (Python):
s=input()
t=input()
max_=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
  max_ = max(max_, c)
print(len(t)-max_)

Solution (Python):
def main():
    s = input()
    t = input()

    len_s, len_t = len(s), len(t)
    num_iter = len_s - len_t + 1
    answer = len_t
    for i in range(num_iter):
        s_sub = s[i : i+len_t]
        count = 0
        for s_i, t_i in zip(s_sub, t):
            if s_i == t_i:
                count += 1
        answer = min(answer, len_t-count)
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
S = list(input())
T = list(input())

s, t = len(S), len(T)
ans = s

for i in range(s-t+1):
    tmp = S[i:i+t]

    cnt = 0
    for i, j in zip(T, tmp):
        if i != j:
            cnt += 1

    ans = min(ans, cnt)

print(ans)

Solution (Python):
S = input()
T = input()

ans = int(10**10)

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

Solution (Python):
s = input()
t = input()

ans = 1000000
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)

Solution (Python):
def rewrite(s, t):
	
	min = len(t)

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

	return min


str_s = input()
str_t = input()
rewrite_word = rewrite(str_s, str_t)
print(rewrite_word)

Solution (Python):
from math import inf
class solution(object):
    def __init__(self, S: str, T:str) -> None:
        self.S = S
        self.T = T
    
    def solve(self)->int:
        ans = inf
        for i in range(0, len(self.S)-len(self.T)+1):
            temp = 0
            for j in range(0, len(self.T)):
                if(self.S[i+j]!=self.T[j]): temp+=1;
            ans = min(ans,temp)
        return ans

if __name__=='__main__':
    S = input()
    T = input()
    problem = solution(S,T)
    ans = problem.solve()
    print(ans)

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

Solution (Python):
S=list(input())
T=list(input())
SS=len(S)
TS=len(T)
ans=TS
for i in range(SS-TS+1):
  cnt=0 
  for j in range(TS):
    
    if T[j] != S[i+j] :
      cnt +=1
  ans=min(cnt,ans)

print(ans)

Solution (Python):
hoge=input()
huga=input()
ans=0
for i in range(len(hoge)+1-len(huga)):
  tmp_ans=0
  for j in range(len(huga)):
    if(hoge[i+j]==huga[j]):
      tmp_ans+=1
  ans=max(ans,tmp_ans)

print(len(huga)-ans)

Solution (Python):
s = input()
t = input()
list = []

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

Solution (Python):
s=input()
t=input()
slen=len(s)
tlen=len(t)
min=tlen
def howdifferent(t1,t):
    count=0
    for i in range(len(t)):
        if t1[i]!=t[i]:
            count+=1
    return count
for i in range(slen-tlen+1):
    t1 = s[i:]
    if howdifferent(t1,t)<min:
        min = howdifferent(t1,t)
print(min)

Solution (Python):
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)
  )
)

Solution (Python):
S = input()
T = input()

min_cnt = float("inf")
for i in range(len(S)-len(T)+1):
    cnt = 0
    dummy = S[i:i+len(T)]
    for j in range(len(dummy)):
        if dummy[j] != T[j]:
            cnt += 1
    if cnt < min_cnt:
        min_cnt = cnt
print(min_cnt)

Solution (Python):
S = input()
T = input()

lt = len(T)
ans = lt
for num in range(len(S) - lt + 1):
    s = S[num:num+lt]
    diff = 0
    for i in range(len(T)):
        if(T[i] != s[i]):
            diff += 1
    ans = min(ans, diff)

print(ans)

Solution (Python):
s = input()
t = input()
ans = len(t)

for i in range(len(s) - len(t) + 1):
    score = 0
    a = s[i : i + len(t) + 1]
    for j in range(len(t)):
        score += a[j] != t[j]
    ans = min(ans, score)

print(ans)

Solution (Python):

S = input()
T = input()

count_max = 0
for i in range(0, (len(S) - len(T) + 1)):
    s = S[i:i+len(T)]
    count = 0
    for j in range(0, len(s)):
        if s[j] == T[j]:
            count += 1
    if count_max < count:
        count_max = count

print(len(T) - count_max)

Solution (Python):
s = input()
t = input()

lens = len(s)
lent = len(t)

kotae = 1000
for i in range(lens-lent+1):
    temp = 0
    for j in range(lent):
        if(s[i+j] == t[j]):
            temp += 1
    kotae = min(kotae,lent-temp)

print(kotae)

Solution (Python):
a = input()
b = input()

arr = []
la = len(a)
lb = len(b)

for i in range(la-lb+1):
    c = a[i:i+lb] 
    cu = 0
    for j in range(lb):
        if c[j] != b[j]:
            cu += 1
    arr.append(cu)
    
print(min(arr))

Solution (Python):
s = list(input())
t = list(input())
n = len(s) - len(t) + 1

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

Solution (Python):
S = input()
T = input()

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

print(len(T)-ans)

Solution (Python):
S = input()
T = input()
ans = 10**10
for k in range(len(S)-len(T)+1):
    U = S[k:k+len(T)]
    temp = 0
    for l in range(len(T)):
        if U[l] != T[l]:
            temp += 1
    ans = min(temp,ans)
print(ans)

Solution (Python):
S = input()
T = input()

if T in S:
    print(0)
else:
    min = 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
        if tmp < min:
            min = tmp
    print(min)

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

Solution (Python):
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)))

Solution (Python):
def solve(s, t):
    n = len(s)
    m = len(t)
    best = m
    for i in range(n-m+1):
        num = 0
        for j in range(m):
            if s[i+j] != t[j]:
                num += 1
        best = min(best, num)
    return best

s = input()
t = input()
print(solve(s, t))

Solution (Python):
s = input()
t = input()

res = len(t)

for i in range(len(s)-len(t)+1):
    tmp=len(t)
    for j in range(len(t)):
        if(s[i+j] == t[j]):
            tmp -= 1
    if res > tmp:
        res = tmp

print(res)

Solution (Python):

S = input()
T = input()

S_list = list(S)
T_list = list(T)
answer = 1000

for i in range(len(S_list)-len(T_list)+1):
    count = 0
    for j in range(len(T_list)):
        if(S_list[i+j] != T_list[j]):
            count +=1
    answer = min(count, answer)
print(answer)

Solution (Python):
from sys import stdin
inp = lambda : stdin.readline().strip()

s = inp()
t = inp()
ans = len(t)
for i in range(len(s)-len(t) + 1):
    curr = 0
    for i,j in zip(s[i:len(t)+i],t):
        if i == j:
            curr += 1
    ans = min(ans, len(t)- curr)
print(ans)

Solution (Python):
from sys import stdin
import math
inp = lambda : stdin.readline().strip()
 
s=inp()
t = inp()
ans = len(t)
for i in range(len(s)-len(t)+1):
    cur = len(t)
    for j in range(len(t)):
        if s[i+j] == t[j]:
            cur -= 1
    ans = min(ans, cur)
print(ans)

Solution (Python):
S = input()
T = input()

ans = len(S)

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

Solution (Python):
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)

Solution (Python):
from sys import exit
import math
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

s = input()
t = input()

ans = 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
    ans = min(ans,cnt)
print(ans)

Solution (Python):
def subst(S, T)-> int:
  lenT = len(T)
  result = lenT
  for i in range(lenT, len(S) + 1):
    tempS = S[i-lenT:i]
    tempResult = 0
    for j in range(lenT):
      if T[j] != tempS[j]:
        tempResult += 1
    if tempResult < result:
      result = tempResult
    
  return result

if __name__ == "__main__":
  S = input()
  T = input()
  print(subst(S, T))

Solution (Python):
def subst(S, T)-> int:
  lenT = len(T)
  result = lenT
  for i in range(len(S) - lenT + 1):
    
    tempResult = 0
    for j in range(lenT):
      if T[j] != S[j + i]:
        tempResult += 1
    if tempResult < result:
      result = tempResult
    
  return result

if __name__ == "__main__":
  S = input()
  T = input()
  print(subst(S, T))

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

Solution (Python):
S = input()
T = input()
ct_f = len(T)
for i in range(len(S)-len(T)+1):
    ct = len(T)
    S_sub = S[i:i+len(T)]
    for j in range(len(T)):
        if S_sub[j] == T[j]:
            ct -= 1

    if ct_f > ct:
        ct_f = ct
        
print(ct_f)

Solution (Python):
S = input()
T = input()
lenS = len(S)
lenT = len(T)
lowest = lenT

for st in range(lenS-lenT+1):
    cnt = lenT
    for i in range(lenT):
        if S[st+i] == T[i]:
            cnt -= 1
    if cnt < lowest:
        lowest =cnt
print(lowest)

Solution (Python):
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)

Solution (Python):
s = list(input())
t = list(input())

li = []
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
	li.append(count)
print(min(li))

Solution (Python):
def check_same_sentence(big_str, small_str):
    num_b = len(big_str)
    num_s = len(small_str)
    ans = 0
    for i in range(num_b - num_s + 1):
        tmp = 0
        for j in range(num_s):
            if big_str[i+j] == small_str[j]:
                tmp += 1
        ans = max(ans, tmp)
    
    return ans

S = input()
T = input()

ans = check_same_sentence(S, T)
print(len(T)-ans)

Solution (Python):
s=input()
t=input()

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

print(ans)

Solution (Python):

s=input()
t=input()
ls=len(s)
lt=len(t)

min_change=lt


for i in range(0,ls-lt+1):
    if(True):
        d = 0
        for j in range(0,lt):
            if(s[i+j]!=t[j]):
                d+=1

        min_change=min(min_change,d)

print(min_change)

Solution (Python):
s = input()
t = input()
minl = len(s)
l = len(t)
for i in range(len(s)-len(t)+1):
    c = 0
    for j in range(l):
        if t[j]!=s[j+i]:
            c += 1
    if minl >= c:
        minl = c
print(minl)

Solution (Python):
s = input()
t = input()
r = len(s)
lon = len(t)
for i in range(len(s)-len(t)+1):
    c = 0
    for j in range(lon):
        if t[j]!=s[j+i]:
            c += 1
    if r >= c:
        r = c
print(r)

Solution (Python):


st = []
for _ in range(2):
    st.append(input())
S=st[0]
T=st[1]

ans=len(T)

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

print(ans)

Solution (Python):


st = []
for _ in range(2):
    st.append(input())
S=st[0]
T=st[1]

ans=len(T)

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

print(ans)

Solution (Python):
import sys; input = sys.stdin.readline
inf = int(1e10)
s = input().strip()
t = input().strip()
n, m = len(s), len(t)
minn = inf
for i in range(0, n-m+1):
	dis = 0
	for j in range(m):
		if s[i+j] != t[j]: dis += 1
	minn = min(minn, dis)
print(minn)

Solution (Python):
S = input()
T = input()

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

Solution (Python):
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)

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

@mt
def slv(S, T):
    ans = INF
    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
        ans = min(ans, t)

    return ans


def main():
    S = read_str()
    T = read_str()
    print(slv(S, T))


if __name__ == '__main__':
    main()

Solution (Python):
"""
https://atcoder.jp/contests/abc177/tasks/abc177_b
"""

def solve(s, t):
    def calc_diff_words(s0, s1):
        cnt = 0
        for w0, w1 in zip(s0, s1):
            if w0 != w1:
                cnt += 1
        return cnt

    def extract_sub(s, t, i):
        return s[i:i + len(t)]

    min = len(s)
    for i in range(len(s) - len(t) + 1):
        ss = extract_sub(s, t, i)
        dw = calc_diff_words(ss, t)
        if dw < min:
            min = dw

    return min

s = input()
t = input()
print(solve(s, t))

Solution (Python):
S = input()
T = input()

S_len = len(S)
T_len = len(T)

ans = T_len

for i in range(S_len - T_len + 1):

    diff = 0

    for j in range(T_len):

        if T[j] != S[i+j]:

            diff += 1

    ans = min(ans, diff)

print(ans)

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

Solution (Python):

S = str(input())
T = str(input())
i = 0
j = 0

Slen = len(S)
Tlen = len(T)
change_min = Tlen

for i in range(Slen - Tlen + 1):
    diff = 0
    for j in range(Tlen):
        if T[j] != S[i + j]:
            diff += 1
    change_min = min(change_min,diff)


print(change_min)

Solution (Python):
import numpy as np

s=np.array(list(input()))
t=np.array(list(input()))

ans = len(t)

for i in range(len(s)-len(t)+1):
    tmp = sum(s[i:i+len(t)] == t)
    if ans > len(t) - tmp:
        ans = len(t) - tmp

print(ans)

Solution (Python):
s =input()
t = input()

minmin = len(t)
for i in range( 0, ( len(s) - len(t)) +1 ):
    tigamoji = 0
    for j in range( len(t)  ):
        if s[j+i] != t[j]:
            tigamoji += 1
    if tigamoji < minmin:
        minmin = tigamoji
print(minmin)

Solution (Python):
s = input()
t = input()

ls = len(s)
lt = len(t)
res = float("inf")
cnt = 0
for i in range(ls - lt+1):
    cnt= 0
    for j in range(lt):
        if s[i + j] != t[j]:
            cnt += 1
    res = min(res,  cnt)
print(res)

Solution (Python):
S = input()
T = input()
ls = len(S)
lt = len(T)
mx = 0
for i in range(ls - lt + 1):
  S2 = S[i:i + lt]
  cnt = 0
  for j in range(lt):
    if S2[j] == T[j]:
      cnt += 1
  mx = max(mx, cnt)

print(lt - mx)

Solution (Python):
S = input()
T = input()
ans = 0
for i in range(len(S)-len(T)+1):
    s = S[i:i+len(T)]
    num = 0
    for j in range(len(T)):
        if s[j] == T[j]:
            num += 1
    if num>ans:
        ans = num
print(len(T)-ans)

Solution (Python):
s = input()
t=input()
s1=len(s)
t1=len(t)
def p(val):
    print(val)


count = 0
for i in range(s1-t1+1):
    miss = 0
    for j in range(t1):
        if s[j+i] != t[j]:
            miss +=1
    if i == 0:
        count = miss
    else:
        if count>=miss:
            count = miss

p(count)

Solution (Python):
s = input()
t = input()

ls = len(s)
lt = len(t)

max_char = lt

for i in range(0, ls - lt+1):
    s2 = s[i:i + lt]
    
    count = 0
    for cs, ct in zip(s2, t):
        if cs != ct:
            count += 1
    max_char = min(count, max_char)
print(max_char)

Solution (Python):
S = input()
T = input()
ans = 0

for i in range(len(S)-(len(T)-1)):
    s = S[i:i+len(T)]
    c = 0
    for j in range(len(T)):
        if s[j] == T[j]:
            c += 1
    ans = max(ans, c)

print(len(T) - ans)

Solution (Python):
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)

Solution (Python):
S = input()
T = input()

ans = len(T)
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
    ans = min(ans, n)
print(ans)

Solution (Python):
S = input()
T = input()
ans = len(T)
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
    ans = min(ans, n)
print(ans)

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

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

Solution (Python):
def sdiff(s1, s2):
  score = 0
  for i in range(0, len(s2)):
    if s1[i] != s2[i]: score += 1
  return score

S = input()
T = input()
Ans = len(T)

for i in range(0, len(S) - len(T) + 1):
  Ans = min(sdiff(S[i:], T), Ans)

print(Ans)

Solution (Python):
"""
int(input())
map(int, input().split())
list(map(int, input().split()))
input()
input().split()
"""


s = input()
t = input()
ans = len(t)

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)

Solution (Python):
S = input()
T = input()

ans = 1000000  



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)