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):
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log  
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
import difflib


def ceil(a, b): return (a + b - 1) // b


inf = float('inf')
mod = 10 ** 9 + 7


def pprint(*A):
    for a in A:     print(*a, sep='\n')


def INT_(n): return int(n) - 1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [I() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    S = ST()
    T = ST()
    m = 0
    for i in range(len(S)-len(T)+1):
        mn = 0
        for j in range(len(T)):
            if S[i+j] == T[j]:
                mn += 1
        m = max(m, mn)
    print(len(T) - m)


if __name__ == '__main__':
    main()

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

scnt = len(s)
tcnt = len(t)

change = 10**3

for i in range (0, scnt - tcnt + 1):
  cnt = 0
  for j in range(tcnt):
    if s[i+j] != t[j]:
      cnt += 1
  if change > cnt:
    change = cnt

print(change)

Solution (Python):
S = input()
T = input()
max = 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
  if max > count:
    max = count
print(max)

Solution (Python):
s= input()
t= input()
len_diff= len(s)- len(t)

top=0
for i in range(len_diff+1):
  test= s[i:]
  count=0
  for j in range(len(t)):
    if test[j]==t[j]:
      count+=1
  if count>top:
    top= count

print(len(t)-top)

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

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

Solution (Python):

import sys

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


S = list(ST())
T = list(ST())
ls = len(S)
lt = len(T)

ans = 1001
for i in range(ls - lt + 1):
    cnt = 0
    for j, t in enumerate(T):
        if S[i + j] != t:
            cnt += 1
    ans = min(ans, cnt)

print(ans)

Solution (Python):
def Substring():
    
    str1 = str(input())
    
    str2 = str(input())

    count_list = []

    for i in range(len(str1) - len(str2) + 1):
        
        count = len(str2)
        
        for j in range(len(str2)):
                        
            if str1[i + j] == str2[j]:
                
                count = count - 1

        count_list.append(count)
        
    print(min(count_list))
        
if __name__ == '__main__':
    Substring()

Solution (Python):
def cin():  return list(map(int,input().split()))

S = input()
T = input()

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

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

maxcount = 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
        maxcount = max(maxcount, count)
print(len(T) - maxcount)

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

ans = 1000

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(ans)

Solution (Python):
def solver(S,T):
    search_len = len(T)
    times = len(S) - len(T) + 1
    min = 1000
    for i in range(times):
        diff = diff_counter(S[i:search_len+i],T)
        if diff < min:
            min = diff
    return min
def diff_counter(S,T):
    counter = 0
    for i in range(len(S)):
        Si = S[i]
        Ti = T[i]
        if Si != Ti:
            counter += 1
    return counter
S = input()
T = input()
print(solver(S,T))

Solution (Python):







from math import *


def _in():
    arr = input().split(' ')
    return arr[0] if len(arr) == 1 else arr


def numCng(s, t):
    if(len(s) != len(t)):
        return 10**9
    cnt = 0
    for i in range(len(s)):
        if(s[i] != t[i]):
            cnt = cnt + 1
    
    return cnt


if __name__ == "__main__":
    s = input()
    t = input()
    n, m = len(s), len(t)
    ans = m
    for i in range(n - m + 1):
        ans = min(ans, numCng(s[i:i + m], t))
    print(ans)

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

l = len(S) - len(T)
f = len(T)

for i in range(l+1):
    temp = 0
    for j in range(len(T)):
        if S[i+j] != T[j]:
            temp += 1
    if f > temp:
        f = temp

print(f)

Solution (Python):
s = input()
t = input()
ls = len(s)
lt = len(t)
ans = 1000
count = 0

for i in range(ls-lt+1):
    ss = s[i:i+lt]
    count = 0
    for i in range(lt):
        if ss[i] == t[i]:
            count += 1
    if ans > lt-count:
        ans = lt-count

print(ans)

Solution (Python):
S = input()
T = input()
s = len(S)
t = len(T)
C = 100000
for i in range(t):
    for j in range(i, s - t + 1 + i):
        if S[j] == T[i]:
            c = i
            for k in range(1, t - i):
                if S[j + k] != T[i + k]:
                    c += 1
            C = min(C, c)
if C == 100000:
    C = t
print(C)

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

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

res = 0
for i in range(ls-lt+1):
    ss =s[i:i+lt]
    cnt = 0
    for j in range(lt):
        if ss[j] == t[j]:
            cnt += 1
    res = max(res, cnt)

print(lt - res)

Solution (Python):
S=input()
T=input()
ls=len(S)
lt=len(T)
cnt2=lt

for i in range(0,ls-lt+1):
  cnt=0
  for ss,tt in zip(S[i:],T):
    if ss!=tt:
      cnt+=1
  
  if cnt<cnt2:
    cnt2=cnt

print(cnt2)

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

nS=len(S)
nT=len(T)

N=nS-nT+1
dfmin=1000
for i in range(N):
    df=0
    for j in range(nT):
        if S[i+j]!=T[j]:
            df+=1
    if df < dfmin:
        dfmin=df
print(dfmin)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    s = input()
    t = input()
    ans = 1001
    for i in range(len(s) - len(t) + 1):
        short_s = s[i:i + len(t)]
        icchi = 0
        for j in range(len(t)):
            if short_s[j] != t[j]:
                icchi += 1
        if icchi < ans:
            ans = icchi
    print(ans)


   

    
if __name__ == "__main__":
    main()

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

for i in range(len(s) - len(t) + 1):
    count = 0
    x = s[i:i+len(t)]
    
    if x == t:
        print(0)
        exit()
    else:
        for j in range(len(x)):
            if x[j] != t[j]:
                count += 1
        count_list.append(count)


print(min(count_list))

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

c = len(S) - len(T)

m = 1000
for i in range(c + 1):
    count = 0
    for s, t in zip(S[i:], T):
        if s != t:
            count += 1
    m = min(m, count)
print(m)

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

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

print(res)

Solution (Python):



import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    S = i2s()
    T = i2s()
    n = len(S)
    m = len(T)
    ans = m
    for i in range(n - m + 1):
        cnt = 0
        for j in range(m):
            cnt += S[i+j] != T[j]
            if cnt >= ans:
                break
        else:
            ans = cnt
        if ans == 0:
            break
    print(ans)
    return

main()

Solution (Python):


S = input()
T = input()
N = len(S)
M= len(T)
ans = N


for j in range(N- M+1):
  change = 0
  for l in range(M):
    if S[j+l] != T[l]:
      change += 1
  ans = min(ans, change)

print(ans)

Solution (Python):
def get_num(s, t):
    cnt = len(s)
    for i in range(len(s)):
        if s[i] == t[i]:
            cnt -= 1
    return cnt


def main():

    s = input()
    t = input()
    len_s, len_t = len(s), len(t)
    ans = len_t
    for i in range(len_s - len_t + 1):
        new_s = s[i:len(t) + i]
        tmp = get_num(new_s, t)
        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

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

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

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

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

Solution (Python):
def ch(s,t):
    list1=[]
    for i in range(len(s)-len(t)+1):
        w=s[i:i+len(t)]
        ct=0
        for j in range(len(t)):
            if w[j]==t[j]:
                ct+=1
        list1.append(ct)
    return(max(list1))
s=input()
t=input()
flag=0
ans=ch(s,t)
print(len(t)-ans)

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

    s = input().rstrip()
    t = input().rstrip()

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


    print(ans)

if __name__ == "__main__":
    resolve()

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

max_cnt = 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
    max_cnt = max(max_cnt, cnt)
print(len(T) - max_cnt)

Solution (Python):
S=list(str(input()))
T=list(str(input()))
ans=10000
for i in range(len(S)-len(T)+1):
    s=0
    for u in range(len(T)):
        if S[i+u]==T[u]:
            s+=1
            
    s=len(T)-s
    ans=min(ans,s)
print(ans)

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

slen=len(s)
tlen = len(t)
min = tlen

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

print(min)

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

result = 1000
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
    result = min(count, result)

print(result)

Solution (Python):

def diff(x,y):
	ret = 0
	for i in range(len(x)):
		if x[i]!=y[i]:
			ret+=1
	return ret
s=input()
t=input()

l = len(t)
ans = float('inf')
for i in range(len(s)):
	if i+l<len(s)+1:
		tmp = diff(s[i:i+l], t)
		ans = min(ans, tmp)
		
print(ans)

Solution (Python):
S = input()
T = input()
t = len(T)
min = 10**3+1
for i in range(len(S)-t+1) :
    count = 0
    Si = S[i:t+i]
    for j in range(t) :
        if Si[j] != T[j] :
            count += 1
    if count < min :
        min = count


print(min)

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

print(ans)

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

def count_common(a,b):
    cnt = 0
    for i in range(len(a)):
        if a[i] == b[i]:
            cnt += 1
    return cnt

cnt = 0

for i in range(len(S) - len(T) + 1):
    cnt = max(cnt, count_common(S[i:i+len(T)],T))

print(len(T)-cnt)

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

ans = len(t)
l = len(s)-len(t)+1
for i in range(l):
    cnt = len(t)
    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()
len_s = len(s)
len_t = len(t)
min = len_t
for i in range(len_s-len_t+1):
    text = s[i:i+len_t]
    kaisu = 0
    for j in range(len(text)):
        if text[j] != t[j]:
            kaisu += 1
    if kaisu < min:
        min = kaisu
print(min)

Solution (Python):





def lg(value):
    flag = False
    flag = True
    if flag:
        print(str(value))



def xt(log):
    lg('★exit() - ' + str(log))
    exit()



def get_results():

    
    lines = list()
    
    lines_count = 2
    
    
    
    
    
    for _ in range(lines_count):
        lines.append(input())

    
    S = lines[0]
    T = lines[1]
    
    
    
    
    
    
    
    
    
    

    result = 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
        if result > cnt:
            result = cnt

    return [result]



def main():
    results = get_results()

    for result in results:
        print(result)



if __name__ == '__main__':
    main()

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


m = len(S)
for i in range(0,len(S)-len(T)+1):
    tgt = S[i:i+len(T)]
    if tgt != T:
        cnt = 0
        for j in range(len(tgt)):
            if tgt[j] != T[j]:
                cnt += 1
        m = min(cnt,m)
    else:
        m = 0
        break

print(m)

Solution (Python):
a=input()
b=input()
mincount=1000000
for i in range(len(a)-len(b)+1) :
  count=0
  for j in range(len(b)) :
    if a[i+j]!=b[j] :
      count+=1
  mincount=min(count,mincount)
print(mincount)

Solution (Python):
S = input().rstrip()
T = input().rstrip()
mn = 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

	if n < mn:
		mn = n

print(mn)

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

ans = float("INF")
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(ans, cnt)

print(ans)

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

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 count > max_count :
        max_count = count
        
print(len(t) - max_count)

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

ans = 100000

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() 

def calc_length(str1, str2):
    length = 0
    for i in range(len(str1)):
        if str1[i] != str2[i]:
            length += 1
    return length

min_length = len(t)
for i in range(len(s)- len(t) + 1):
    l = calc_length(s[i:i+len(t)], t)
    if l < min_length:
        min_length = l

print(min_length)

Solution (Python):
import sys
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))


def f(s, t):
	
	ans = 0
	for i in range(len(t)):
		ans += (s[i] != t[i])
	return(ans)

def main():
	s = input().strip(); t = input().strip()
	ans = f(s, t)

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


if __name__ == "__main__":
	main()

Solution (Python):
s = input()
t = input()
num = 10 ** 10
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
    num = min(num, cnt)

print(num)

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

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

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

result = 0
for i in range(len(s) - len(t) + 1):
    c = 0
    for m in range(len(t)):
        if t[m] == s[m+i]:
            c+=1
    if c > result:
        result = c
print(len(t) - result)

Solution (Python):
def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)

    ans = 10**9

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


main()

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

diff = len(S) - len(T)
min_cnt = 1000
for i in range(0,diff+1):
  cnt = 0
  for j in range(len(T)):
    if T[j] != S[i+j]:
      cnt += 1
  if cnt < min_cnt:
    min_cnt = cnt
    if cnt == 0:
      break
    
print(min_cnt)

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

if T in S:
  print(0)
  exit()

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

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

N = len(S)
M = len(T)

ans = []

for i in range(N-M+1):
    cnt = 0
    for j in range(M):
        if S[i+j] != T[j]:
            cnt += 1
    ans.append(cnt)

print(min(ans))

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

n = len(S)
m = len(T)

ans = m

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

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

def check(a,b):
    s = 0
    for i,j in zip(a,b):
        s += i!=j
    return s
ans = 10**6
for i in range(len(s)):
    a = s[i:]
    if len(a) >= len(t):
        ans = min(ans,check(t,a[:len(t)]))
print(ans)

Solution (Python):
s = str(input())
t = str(input())
total = 0
for i in range(len(s)-len(t)+1):
  u = s[i:i+len(t)]
  sum = 0
  for j in range(len(t)):
    if u[j] == t[j]:
      sum += 1
  total = max(sum,total)

print(len(t)-total)

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

min_count = 1000
for idx in range(len(S) - len(T) + 1):
    s = S[idx:idx+len(T)]
    count = sum([1 if tc!=sc else 0 for tc, sc in zip(T, s)])
    min_count = min(min_count, count)

print(min_count)

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

for i in range(len(S) - len(T)):
  tmp = 0
  for j in range(len(T)):
    if S[j+i] == T[j]:
      tmp += 1
  if tmp > max_count:
    max_count = tmp

if len(S) == len(T):
  tmp = 0
  for j in range(len(T)):
    if S[j] == T[j]:
      tmp += 1
  if tmp > max_count:
    max_count = tmp

print(len(T) - max_count)

Solution (Python):
s = input()
t = input()
lens, lent = len(s), len(t)
minimum = float('inf')
for i in range(lens - lent + 1):
  diff = 0
  for j in range(lent):
    if s[i + j] != t[j]:
      diff += 1
  minimum = min(minimum, diff)
  if minimum == 0:
    break
print(minimum)

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

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

Solution (Python):

S = input()
T = input()

max_cnt = 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

    if max_cnt < cnt:
        max_cnt = cnt

print(len(T) - max_cnt)

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

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

print(Min)

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

Solution (Python):
import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    s = ns()
    t = ns()
    ans = len(t)
    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, len(t) - tmp)
    print(ans)


if __name__ == '__main__':
    main()

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

c = len(S) - len(T)

m = 10000
for i in range(c + 1):
    count = 0
    for s, t in zip(S[i:], T):
        if s != t:
            count += 1
    m = min(m, count)
print(m)

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

Solution (Python):
import sys
from io import StringIO
import unittest


def resolve():
    s = input()
    t = input()

    num = len(t)
    ans = 1000

    for i in range(0, len(s) - num + 1):
        tmp = 0
        for a, b in zip(s[i:(i + num)], t):
            if a != b:
                tmp += 1

        if tmp < ans:
            ans = tmp

    print(ans)

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """cabacc
abc"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """codeforces
atcoder"""
        output = """6"""
        self.assertIO(input, output)


if __name__ == "__main__":
    
    resolve()

Solution (Python):
import sys
from io import StringIO
import unittest
import os


sys.setrecursionlimit(999999999)



def resolve(test_def_name=""):
    s_s = input()
    t_s = input()

    ans = 0

    for i in range(len(s_s) - len(t_s) + 1):
        work = 0

        for j in range(len(t_s)):
            if s_s[i + j] == t_s[j]:
                work += 1
        ans = max(ans, work)

    print(len(t_s) - ans)



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """cabacc
abc"""
        output = """1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """codeforces
atcoder"""
        output = """6"""
        self.assertIO(test_input, output)

    
    def test_original(self):
        pass



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

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

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

print(ans)

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

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

print(ans)

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


r = []
n = len(s) - len(t) + 1

for i in range(n):
    w_w = len(t)
    for j in range(len(t)):
        
        if s[i+j] == t[j]:
            w_w -= 1
    
    r.append(w_w)
print(min(r))

Solution (Python):
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[j+i] != t[j]:
            count += 1
    ans = min(ans, count)
print(ans)

Solution (Python):
def resolve():
    s = input()
    t = input()
    ans = 10**18
    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
        if ans > a:
            ans = a

    print(ans)

resolve()

Solution (Python):
s=input()
t=input()
u=[0]*(len(s)-len(t)+1)

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
    u[i]=c
print(len(t)-max(u))

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

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

ans = 1000

for i in range(lens - lent + 1):
    k = 0
    for j in range(i,lent + i):
        if s[j] != t[j-i]:
            k += 1
    ans = min(ans,k)

print(ans)

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

l=[False]*len(s)
c=0
m=0
for x in range(len(s)-len(t)+1):
     c=0
     for y in range(len(t)):
          w=s[x:x+len(t)]
          if w[y]==t[y]:c+=1
     m=max(m,c)
print(len(t)-m)

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

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

ans = 1000

for i in range(u):
    num = 0
    for j in range(len(t)):
        if s[i+j] != t[j]:
            num += 1
    if num <= ans:
        ans = num

print(ans)

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = np.array(list(readline().rstrip()), np.int32)
T = np.array(list(readline().rstrip()), np.int32)

LS, LT = len(S), len(T)

x = 0
for s in range(LS - LT + 1):
    same = np.sum(S[s:s + LT] == T)
    x = max(x, same)

print(len(T) - x)

Solution (Python):
S = list(input())
T = list(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)

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

Solution (Python):

import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    S = input()
    N = len(S)
    T = input()
    M = len(T)
    ans = INF
    for i in range(N-M+1):
        cnt = 0
        for k in range(M):
            if S[i+k] != T[k]:
                cnt += 1
        ans = min(ans, cnt)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
S=input()
T=input()
cnt_min=1001
for i in range(len(S)-len(T)+1):
  
  s=S[i:i+len(T)]
  cnt=0
  for i,s_ in enumerate(s):
    if T[i] != s_:
      cnt+=1
  if cnt_min > cnt:
    cnt_min = cnt

print(cnt_min)

Solution (Python):
s = input()
t = input()
lent = len(t)
ans = []
if len(s) == lent:
    ans1 = 0
    for s1, t1 in zip(s, t):
        ans1 += (s1==t1)
    ans.append(ans1)
else:
    for i in range(len(s) - lent):
        ss = s[i:i+lent]
        ans1 = 0
        for s1, t1 in zip(ss, t):
            ans1 += (s1==t1)
        ans.append(ans1)
print(lent-max(ans))

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

min = 10000
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
  
  if min > count:
    min = count

print(min)

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

min_score = len(t)
for i in range(len(s) - len(t)+1):
  s_p = s[i:i+len(t)]
  count_wrong = 0
  for j in range(len(t)):
    if t[j] != s_p[j]:
      count_wrong += 1
  min_score = min(count_wrong, min_score)

print(min_score)

Solution (Python):
s = input()
t = input()
times = len(s) - len(t) + 1
ans = len(t)
if t in s:
  ans = 0
else:
  for i in range(times):
    ans_tmp = 0
    for j in range(len(t)):
      if t[j] != s[i+j]:
        ans_tmp += 1
    if ans_tmp <= ans:
      ans = ans_tmp
print(ans)

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

if T in S:
    print(0)
else:
    matched = 0
    for i in range(len(S)-len(T)+1):
        matched_work = 0
        for j in range(len(T)):
            if T[j] == S[i+j]:
                matched_work += 1
        if matched_work > matched:
            matched = matched_work
    print(len(T)-matched)

Solution (Python):
s=list(input())
t=list(input())
cnt=0
newT=[]
ans=[]
for i in range(len(s)):
    try:
        cnt=0
        for j in range(len(t)):
            if s[j+i]==t[j]:
                cnt+=1
        
        ans.append(len(t)-cnt)
    except:
        break

print(min(ans))

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

l_s = len(s)
l_t = len(t)

change = l_t
for i in range(l_s - l_t + 1):
    change_temp = 0
    for j in range(l_t):
        if s[i+j] != t[j]:
            change_temp += 1

    change = min(change, change_temp)

print(change)

Solution (Python):
def itti(S, T):
    ans = 0
    for i in range(len(S)):
        if S[i] == T[i]:
            ans += 1
    return ans


S = input()
T = input()

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


print(len(T)-ans)

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


m=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
    m=max(m,c)

print(len(t)-m)

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