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


ans = len(t)
for i in range(0, 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()

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

ans = float('inf')
for i in range(len(s) - len(t) + 1):
    num = compare(s[i:(i+len(t))], t)
    if num < ans:
        ans = num

print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7

    s=SI()
    t=SI()
    a=len(s)
    b=len(t)
    ans=b
    for i in range(a-b+1):
        res=b
        for j in range(b):
            if s[i+j]==t[j]:
                res-=1
        ans=min(ans,res)
    print(ans)
            
        
if __name__=="__main__":
    main()

Solution (Python):
s = input()
t = input()
n = len(s)
m = len(t)

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

Solution (Python):
s = input()
t = input()
most = float("inf")
for i in range(len(s)-len(t)+1):
    count = 0
    for j in range(i,i+len(t)):
        if s[j] != t[j-i]:
            count += 1
    most = min(most,count)
print(most)

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

min_c = 10000000

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

    min_c = min(c,min_c)
print(min_c)

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

Solution (Python):
s=list(input())
t=list(input())
xs=len(s)
xt=len(t)
count=1000
for i in range(xs-xt+1):
    temp=0
    for j in range(xt):
        if s[i+j]!=t[j]:
            temp+=1
    count=min(temp,count)
print(count)

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

ls = len(S)
lt = len(T)
ans = lt
for i in range(ls):
    dif = 0
    for j in range(lt):
        if ls <= i+j:
            break
        if S[i+j] != T[j]:
            dif += 1
    else:
        ans = min(ans,dif)

print(ans)

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

res = float('inf')
nt = len(T)
ns = len(S)
for i in range(ns-nt+1):
    count = 0
    for j in range(nt):
        if T[j] != S[i+j]:
            count +=1 
    res = min(res, count)
print(res)

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

result = 10 ** 9
for i in range(len(s) - len(t) + 1):
  tmp = 0
  for i, c in enumerate(s[i:i+len(t)]):
    if c != t[i]:
      tmp += 1
  result = min(result, tmp)

print(result)

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

Solution (Python):
import sys

def solve(a,b):

	count=0
	for g in range(len(a)):
		if(a[g]!=b[g]):
			count+=1
	return count

S=sys.stdin.readline().strip()
T=sys.stdin.readline().strip()

l=len(T)

ans=100000

for a in range(len(S)-len(T)+1):
	ans=min(ans,solve(S[a:a+l],T))

print(ans)

Solution (Python):
import sys

s=input()
t=input()
lol=float('inf')
for i in range(len(s)-len(t)+1):
    ch=0
    
    for j in range(len(t)):
        
        
        if s[i+j]!=t[j]:
            ch+=1
    lol=min(lol,ch)
print(lol)

Solution (Python):
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 main():
    S = input()
    T = input()
    ans = len(T)
    for start in range(len(S) - len(T) + 1):
        cnt = 0
        for i in range(len(T)):
            if S[start + i] != T[i]:
                cnt += 1
        ans = min(ans, cnt)
    print(ans)


if __name__ == '__main__':
    main()

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

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

ans = 10**9

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

    ans = min(ans, tmp)

print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

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

s = input()
t = input()
n = len(t)
ans = 10 ** 10
for i in range(len(s) - n + 1):
    ans = min(ans, check(s[i: i + n], t))
print(ans)

Solution (Python):
S = input()
T = input()
ans = 10**10

len_s = len(S)
len_t = len(T)

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

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

ans = 0

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 = max(ans, ansi)

print(len(T) - ans)

Solution (Python):
import sys
import math
import collections
import bisect
import itertools
import decimal




INF = 10 ** 20
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))




def main():
    s = list(input())
    t = list(input())

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

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

S=input()
T=input()
ls=len(S)
lt=len(T)
ans=float('inf')
for i in range(ls-lt+1):
    ans_=0
    for j in range(lt):
        if S[i+j]!=T[j]:
            ans_+=1
    ans=min(ans,ans_)
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()
nt = len(t)
def check(a,b):
    cnt = 0
    for sa,sb in zip(a,b):
        if sa != sb:
            cnt += 1
    return cnt
ans = 1 << 50
for i in range(nt,len(s)+1):
    s_p = s[i-nt:i]
    
    ans = min(check(s_p,t),ans)
print(ans)

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

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

Solution (Python):

import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    
    
    
    
    
    
    s = input()
    t = input()
    
    ans = len(s)
    st = set()
    for i in range(len(s) - len(t)+1):
        anss = 0
        for j in range(len(t)):
            if t[j] != s[i+j]:
                anss += 1
        ans = min(ans, anss)
    print(ans)

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

Solution (Python):
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10
    S=input()
    T=input()
    min_change = 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
        min_change = min(min_change,tmp)
    print(min_change)




    
main()

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

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

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

Solution (Python):
def main():
	S = input()
	T = input()
	ls = len(S)
	lt = len(T)
	ans = []
	for i in range(ls - lt + 1):
		cnt = 0
		for j in range(lt):
			if S[i + j] != T[j]:
				cnt += 1
		ans.append(cnt)
	print(min(ans))

main()

Solution (Python):
import sys, math
import io, os

from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal


INF = float('inf')
mod = int(1e9) + 7


s=data()
t=data()
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)
out(ans)

Solution (Python):
S = input()
T = input()
def f(s,t):
    ret = 0
    for c,d in zip(s,t):
        if c != d:
            ret += 1
    return ret
ans = len(T)
for i in range(0, len(S)-len(T)+1):
    ans = min(ans, f(S[i:i+len(T)], T))
print(ans)

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

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

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

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

print(ans)

Solution (Python):
S = input()
T = input()
N, M = len(S), len(T)
ma = 0
for i in range(N-M+1):
    c = 0
    for j in range(M):
        if S[i+j] == T[j]:
            c += 1
    ma = max(ma, c)

print(M - ma)

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

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

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

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

ANS=10000
LENT=len(T)
LENS=len(S)

for i in range(LENS-LENT+1):
    score=0
    for j in range(LENT):
        if T[j]!=S[i+j]:
            score+=1

    
    ANS=min(ANS,score)

print(ANS)

Solution (Python):
def main():
    s = input()
    t = input()
    n,m = len(s),len(t)
    c = 0
    for i in range(n-m+1):
        cnt = 0
        for j in range(m):
            if s[i+j] == t[j]:
                cnt += 1
        if cnt > c:
            c = cnt
    print(m-c)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

s = list(input())
t = list(input())

ans = float("inf")

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

print(ans)

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

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

Solution (Python):
S = input().strip()
T = input().strip()
k = len(T)
dmin = len(S)
for i in range(len(S)-k+1):
    cnt = 0
    for j in range(k):
        if S[i+j]!=T[j]:
            cnt += 1
    dmin = min(dmin,cnt)
print(dmin)

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

s = ns()
t = ns()

ss = len(s)
tt = len(t)
ans = 0

for i in range(ss-tt+1):
    a = 0
    for j in range(tt):
        if s[i+j] == t[j]:
            a += 1
    ans = max(a,ans)

print(tt-ans)

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

Solution (Python):
S = input()
T = input()
ans = float('inf')
for i in range(len(S)):
    tmp_ans = 0
    for j in range(len(T)):
        if j + i >= len(S):
            break
        if S[i + j] != T[j]:
            tmp_ans += 1
    else:
        ans = min(ans, tmp_ans)
print(ans)

Solution (Python):


S = input()
T = input()

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

Solution (Python):
s = input()
s = list(s)
t = input()
t = list(t)
ans = 10**9
k = 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 = min(ans,k)
print(ans)

Solution (Python):
S = input()
T = input()
len_S, len_T = len(S), len(T)
result = 10**8
for i in range(len_S-len_T+1):
  R = 0
  for j in range(len_T):
    if S[i+j] != T[j]:
      R += 1
  result = min(result, R)
print(result)

Solution (Python):
import os
import sys
import math
import heapq
from decimal import *
from io import BytesIO, IOBase
from collections import defaultdict, deque

def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

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

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

ans = 10 ** 19
for i in range(len(s) - len(t) + 1):
  num = 0
  for a, b in zip(s[i:], t):
    if a != b:
      num += 1
  ans = min(ans, num)
  
print(ans)

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

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

ans = float('inf')
for i in range(LS - LT + 1):
    cnt = 0
    for k in range(LT):
        if S[i+k] != T[k]:
            cnt += 1
    ans = ans if ans < cnt else cnt
print(ans)

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

Solution (Python):
s = str(input())
t = str(input())
ans = 10000
for i in range(len(s)-len(t)+1):
  num = 0
  for j in range(len(t)):

    if s[i+j] != t[j]:
      num += 1
  ans = min(ans,num)
print(ans)

Solution (Python):
def main():
    S = input()
    T = input()
    l = len(T)
    m = l
    for i in range(len(S)-l+1):
        r = 0
        for j in range(l):
            if S[i+j] != T[j]:
                r += 1
        if r < m:
            m = r
    return m
print(main())

Solution (Python):
def main():
    s = input()
    t = input()
    p = 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
        if p < tmp:
            p = tmp
    print(len(t)-p)

if __name__ == "__main__":
    main()

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

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

ans = lt
for i in range(ls - lt + 1):
    cnt = 0
    for es, et in zip(s[i:i+lt], t):
        cnt += es != et

    ans = min(ans, cnt)

print(ans)

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

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

Solution (Python):
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy


MOD = 10 ** 9 + 7



s = input()
t = input()

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

print(vmin)

Solution (Python):
s = input()
t = input()
n_t = len(t)
n_s = len(s)
ans = n_s
for i in range(n_s):
    if i+n_t <= n_s:
        time = 0
        for j in range(n_t):
            if s[i+j] != t[j]:
                time+= 1
        ans = min(ans,time)
print(ans)

Solution (Python):
s = list(input())
t = list(input())
ls, lt = len(s), len(t)
ans = lt
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, lt - cnt)
print(ans)

Solution (Python):
def examA():
    D,T,S = LI()
    if (D-1)//S<T:
        ans = "Yes"
    else:
        ans = "No"
    print(ans)
    return

def examB():
    S = SI()
    T = SI()
    s = len(S)
    t = len(T)
    ans = t
    for i in range(s-t+1):
        cnt = 0
        for j in range(t):
            if S[i+j]!=T[j]:
                cnt += 1
        ans = min(ans,cnt)

    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examB()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
S = input()
T = input()
ans = 1<<60
for i in range(len(S)-len(T)+1):
    s_ = S[i:i+len(T)]
    a = 0
    for s, t in zip(s_, T):
        a += s!=t
    if ans > a:
        ans = a
print(ans)

Solution (Python):
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rf = lambda: map(float, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

s, t = rr(), rr()
lent = len(t)
ans = inf
for i in range(len(s)-lent+1):
    cnt = 0
    for a, b in zip(s[i:i+lent], t):
        if a!=b:
            cnt += 1
    ans = min(ans, cnt)
print(ans)

Solution (Python):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


ans = INF
s = str_inp()
t = str_inp()

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()
len_s = len(s)
len_t = len(t)

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

Solution (Python):



from fractions import gcd
from itertools import combinations,permutations,accumulate, product 

from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect














import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7


from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
s = input()
t = input()
ans = len(t)
for i in range(len(s)-len(t)+1):
    nya = s[i:i+len(t)]
    
    p = 0
    for j in range(len(nya)):
        if t[j] == nya[j]:
            pass
        else:
            p += 1
    ans = min(ans,p)
print(ans)

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

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

ns=len(s)
nt=len(t)

ans=10**4
for i in range(ns-nt+1):
    temp=0
    for j in range(nt):
        if t[j]!=s[i+j]:
            temp+=1
    ans=min(ans,temp)

print(ans)

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

ans = len(T)
for b in range(len(S)):
    e = b + len(T)
    if e > len(S):
        break
    ans = min(ans, sum(0 if s == t else 1 for s, t in zip(S[b:e], T)))
    
print(ans)

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

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

print(answer)

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

Solution (Python):
def resolve():
    S = input()
    T = input()
    ans = len(T)
    for i in range(len(S)- len(T) + 1):
        count = S[i:i+len(T)]
        no = 0
        for j in range(len(count)):
            if count[j] != T[j]:
                no += 1
        if ans > no:
            ans = no
    print(ans)
resolve()

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")

INF = float("inf")


S = list(input())[:-1]
T = list(input())[:-1]
N = len(S)
n = len(T)
MIN = 10000
for i in range(N-n+1):
    c = 0
    for j in range(n):
        if S[i+j] != T[j]:
            c += 1
    MIN = min(MIN,c)
print(MIN)

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

n = len(s)
m = len(t)

res = m

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

print(res)

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    T = iss()
    s_len = len(S)
    t_len = len(T)

    ret = INF
    for i in range(s_len - t_len + 1):
        tmp = S[i:i + t_len]
        l = 0
        for j in range(t_len):
            if tmp[j] != T[j]: l += 1
        ret = min(ret, l)
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
import copy
import numpy as np


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

    if cnt < ans:
        ans = cnt

print(ans)

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

ans = len(t)
for i in range(len(s)-len(t)+1):
    same = 0
    for g in range(len(t)):
        if s[i+g] == t[g]:
            same += 1
    ans = min(len(t)-same, ans)

print(ans)

Solution (Python):

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

s = input().strip()
t = input().strip()
n = len(s)
m = len(t)
ans = float('inf')
for i in range(n-m+1):
    ct = 0
    for j in range(m):
        if s[i+j] != t[j]:
            ct += 1
    ans = min(ans,ct)
print(ans)

Solution (Python):
def diff(a, b):
  res = 0
  for (ca, cb) in zip(a, b):
    if ca != cb:
      res += 1
  return res

def solve(s, t):
  res = len(t)
  for i in range(0, len(s) - len(t) + 1):
    res = min(res, diff(s[i : i + len(t)], t))
  return res

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

Solution (Python):
import math
import fractions
import collections
import itertools
S=list(input())
T=list(input())
ans=float("inf")
num=0
for i in range(0,len(S)-len(T)+1):
    num=0
    for j in range(len(T)):
        if S[i+j]!=T[j]:
            num=num+1
    ans=min(ans,num)
    
print(ans)