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):
from sys import stdin,stdout
from collections import defaultdict
import math
from bisect import bisect
input=stdin.readline

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

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

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

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

ans = 1001

if T in S:
    print(0)
    exit()
else:
    for i in range(len(S) - len(T) + 1):
        count = 0
        s = S[i:i + len(T)]
        for j in range(len(T)):
            if s[j] != T[j]:
                count += 1
        if ans > count:
            ans = count
    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):
  u = s[i: i+len_t]
  d = sum(0 if c1 == c2 else 1 for c1, c2 in zip(t, u))
  ans = min(d, ans)

print(ans)

Solution (Python):

S=input()
T=input()

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

for i in range(M-N+1):
    tmp=S[i:i+N]
    
    cnt=0
    for j in range(N):
        if tmp[j]==T[j]:
            cnt +=1
    ans = max(ans,cnt)

print(N-ans)

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
    if ans>tmp:
        ans=tmp
print(ans)

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

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

print(cnt_min)

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

min = 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 += 1
    if dif < min:
        min = dif
    

print(min)

Solution (Python):
S = input()
T = input()
lenT = len(T)
lenS = len(S)
lsS = []
for i in range(lenS-lenT+1):
    lsS.append(S[i:i+lenT])
ans = 1000
for st in lsS:
    ii = 0
    for i in range(lenT):
        if st[i] != T[i]:
            ii += 1
    ans = min(ans,ii)
print(ans)

Solution (Python):


s = input()
t = input()
min_count = 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
    min_count = min(count, min_count)
    if min_count == 0:
        break
print(min_count)

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

ans = 10**18
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
    ans = min(temp,ans)
print(ans)

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

def c(s, t):
  
  r = 0
  for i in range(n):
    if s[i] == t[i]:
      r += 1
  return n - r

ans = n
for i in range( len(S) - n + 1):
  temp = c(S[i:i+n],T)
  ans = min( ans, temp)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    S = input().rstrip()
    T = input().rstrip()
    ans = 0
    for i in range(len(S)-len(T)+1):
        CNT = 0
        for j in range(len(T)):
            if S[i+j] == T[j]:
                CNT += 1
        ans = max(ans, CNT)
    print(len(T) - ans)

if __name__ == '__main__':
    main()

Solution (Python):
s = input()
t = input()
ans = 10000
if t in s:
    print(0)
    exit()

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

print(ans)

Solution (Python):
S = input()
T = input()
ind = 0
cmax = 0
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
    if(count > cmax):
        ind = i
        cmax = count
print(len(T)-cmax)

Solution (Python):


S=input()
T=input()

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

ans=lt

for i in range(ls-lt+1):
    ss=S[i:i+lt]
    c=0
    for j in range(lt):
        if ss[j]!=T[j]: c+=1

    if c<ans: ans=c

print(ans)

Solution (Python):
s = str(input())
t = str(input())
c = list()
for i in range(len(s)-len(t)+1):
    cnt = 0
    for j in range(len(t)):
        if t[j] == s[i+j]:
            cnt = cnt + 1
        else:
            continue
    c.append(cnt)
print(len(t)-max(c))

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

s = readline().rstrip().decode('utf-8')
t = readline().rstrip().decode('utf-8')
ls = len(s)
lt = len(t)
ans = 10**18
for i in range(ls-lt+1):
    res = 0
    for j in range(lt):
        if s[i+j] != t[j]:
            res += 1
    ans = min(ans,res)

print(ans)

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

ans = 10000
for i in range(len(S)-len(T)+1):
    count = 0
    for elts, eltt in zip(S[i:i+len(T)], T):
        if elts != eltt:
            count += 1
    ans = min(ans, count)

print(ans)

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

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

print(ans)

Solution (Python):
if __name__ == '__main__':
    s = input()
    t = input()

    min = len(t)

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

Solution (Python):
import math
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
 


s = input()
t = input()
ans = 0

for i in range(len(t)):
    if t[i] != s[i]:
        ans += 1

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

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

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

ans = 0

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

print(t - ans)

Solution (Python):
I=lambda:list(map(int,input().split()))
s=list(input())
t=list(input())
ans=len(t)
for i in range(len(s)-len(t)+1):
	temp=s[i:i+len(t)]
	te=0
	for j in range(len(t)):
		if temp[j]!=t[j]:
			te+=1
	ans=min(te,ans)
print(ans)

Solution (Python):
s = input().strip()
t = input().strip()
R = 10**18
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
    R = min(r, R)
print(R)

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

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

Solution (Python):
S=input()
T=input()
ls =len(S)
lt=len(T)
maxn=0
for i in range(ls-lt+1):
  tmp=0
  for j in range(lt):
    if T[j]==S[i+j]:
      tmp+=1
  if tmp >maxn:
    maxn=tmp
print(lt-maxn)

Solution (Python):
S=input()
T=input()
length=len(T)
min_=10000
for i in range(0,len(S)-length+1):
    count=0
    for j in range(length):
        if S[i+j]!=T[j]:
            count+=1
    min_=min(min_,count)
print(min_)

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

Solution (Python):


s = input()
t = input()

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

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

n = len(t)

i = 0
j = 0

a = 10000

for i in range(len(s)-n+1):
    u = s[i:i+n]
    b = 0
    for j in range(n):
        if t[j] != u[j]:
            b += 1
    a = min(a, b)

print(a)

Solution (Python):
import math
import itertools
import sys
s = input()
t = input()
cnt = len(t)
for i in range(len(s)-len(t)+1):
    tmp = s[i:len(t)+i]
    tcnt = 0
    for j in range(len(tmp)):
        if(tmp[j] != t[j]):
            tcnt += 1
    cnt = min(cnt, tcnt)
print(cnt)

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

ans = 10000

for i in range(len(S)-len(T)+1):
    Tcheck = S[i:len(T)+i]


    tmp = 0
    for j in range(len(Tcheck)):
        if(T[j] != Tcheck[j]):
            tmp += 1
    
    ans = min(ans, tmp)

print(ans)

Solution (Python):
s=input()
t=input()
n=len(t)
lens=len(s)
mx=0
for i,j in enumerate(s):
    if i+n>len(s):
        break
    sm=0
    for k,l in enumerate(t):
        if l==s[i+k]:
            sm+=1
    mx=max(sm, mx)

print(len(t)-mx)

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

S = rs()
T = rs()

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

Solution (Python):

import sys


def solve(S: str, T: str):
    min_change = 100000000

    S = [s for s in S]
    T = [t for t in T]

    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if j == 0:
                c = 0
            if len(S) <= i + j:
                break
            if S[i+j] != t:
                c += 1
            if len(T) == j + 1:
                min_change = min(min_change, c)

    print(min_change)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  
    T = next(tokens)  
    solve(S, T)

if __name__ == '__main__':
    main()

Solution (Python):
sta=list(input())
stb=list(input())
max=0
for a in range(len(sta)-len(stb)+1):
    max1=0
    for b in range(len(stb)):
        if sta[a+b]==stb[b]:
            max1+=1
    if max1>max:
        max=max1
print(len(stb)-max)

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

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

print(str(m))

Solution (Python):
s=input()
t=input()
ans=999999
def check(x,y):
    ret=0
    for i in range(len(x)):
        if x[i]!=y[i]:
            ret+=1
    return ret
for i in range(len(s)-len(t)+1):
    ans=min(check(s[i:i+len(t)],t),ans)
print(ans)

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

def compute_overlap(W1, W2):
    return sum([w1 != w2 for w1, w2 in zip(W1, W2)])

res = len(T)
for i in range(len(S)-len(T)+1):
    rep = compute_overlap(S[i:i+len(T)], T)
    res = min(res, rep )

print(res)

Solution (Python):
s = input()
t = input()
s_list = []
j = 0

for i in range(len(t),len(s)+1):
    s_list.append(s[j:i])
    j += 1

differ = len(t)
mojiretu = ''
for i in range(len(s_list)):
    tmp = 0
    for j in range(len(t)):
        if s_list[i][j] != t[j]:
            tmp += 1
    if tmp < differ:
        differ = tmp
        mojiretu = s_list[i]
    tmp = 0

print(differ)

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

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

Solution (Python):
s = input()
t = input()
ans = 9999
for i in range(len(s) - len(t) + 1):
    diff = 0
    for si, ti in zip(s[i:i+len(t)], t):
        if si != ti:
            diff += 1
    ans = min(ans, diff)
print(ans)

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

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

ans = 10 ** 10
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
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    S = SI()
    T = SI()
    ls, lt = len(S), len(T)
    ans = 1100
    for i in range(ls-lt+1):
        tmp = 0
        tS = S[i:i+lt]
        for k, t in zip(tS, T):
            if k != t:
                tmp += 1
        ans = min(ans, tmp)
    print(ans)




if __name__ == "__main__":
    main()

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


if __name__ == "__main__":
    main()

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

size = len(T)
n = len(S)
ans = size

for i in range(n-size+1):
    t = S[i:i+size]
    v = sum([k!=j for k, j in zip(T, t)])
    ans = min(v, ans)

print(ans)

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

gap = 999999999999

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
  gap = min(temp, gap)

print(gap)

Solution (Python):






import math
import statistics
import numpy as np
import queue
import itertools
import functools 


TBMod = int(1e+9 + 7)

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

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

Solution (Python):
S = input()
T = input()
D = [0] * len(S)
for i, _ in enumerate(S):
  if i + len(T) > len(S):
    D[i] = len(T)
    continue
  for j, t in enumerate(T):
    D[i] += 1 if S[i + j] != t else 0
print(min(D))

Solution (Python):
import os
import heapq
import sys,threading
import math
import operator
from collections import defaultdict
from io import BytesIO, IOBase

sys.setrecursionlimit(10 ** 5)
threading.stack_size(2**27)


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""


def inpt():
    return [int(k) for k in input().split()]


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






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

if __name__ == "__main__":
    main()

Solution (Python):
S = input()

T = input()

ans = float("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
    ans = min(tmp, ans)
print(ans)

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

print(len(T)-m)

Solution (Python):
s = input()
t = input()
x = len(s) - len(t) + 1
y = len(t)
lst = []
for i in range(x):
  c = 0
  for j in range(y):
    if (t[j] != s[j + i]):
      c = c + 1
  lst.append(c)
lst2 = sorted(lst)
print(lst2[0])

Solution (Python):
'''
Created on 2020/08/29

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  S=pin()[:-1]
  T=pin()[:-1]
  t=len(T)
  ans=len(T)
  for i in range(len(S)-t+1):
    u=S[i:i+t]
    cnt=0
    for j in range(t):
      if u[j]!=T[j]:
        cnt+=1
    ans=min(ans,cnt)
  print(ans)
  return 
main()

Solution (Python):
import copy

s = input()
t = input()

sn = len(s)
tn = len(t)
answer = int(copy.deepcopy(tn))

for i in range(sn-tn+1):
    sk = s[i:i+tn]
    count = 0
    for j in range(tn):
        if sk[j] != t[j]:
            count += 1
    if count < answer:
        answer = count

print(answer)

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

mn = 10000
for i in range(len(s)-len(t)+1):
    s_ = s[i:i+len(t)]
    ne = 0
    for j in range(len(t)):
        if s_[j] != t[j]:
            ne += 1
    if ne < mn:
        mn = ne

print(mn)

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

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

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

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

def diff(a, b):
    return sum(aa != bb for aa, bb in zip(a, b))

answer = min( diff(S[i: i+len(T)], T) for i in range(len(S)-len(T)+1) )
print(answer)

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

Solution (Python):
S = input()
T = input()
res = []
for i in range(len(S) - len(T) + 1):
  s = S[i:i+len(T)]
  cnt = 0
  for i in range(len(s)):
    if s[i] != T[i]:
      cnt += 1
  res.append(cnt)

print(min(res))

Solution (Python):
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext

def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    s = s_input()
    t = s_input()

    min_count = INF

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

    print(min_count)

if __name__ == '__main__':
    main()

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

Solution (Python):
import sys

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

ls = len(S)
lt = len(T)
match = 0
for i in range(ls - lt + 1):
    tmp = 0
    for j in range(lt):
        if S[i+j] == T[j]:
            tmp += 1
    match = max(match, tmp)

print(lt - match)

Solution (Python):
LI = lambda: list(map(int, input().split()))

S = input()
T = input()


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


if __name__ == "__main__":
    main()

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

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

print(ans)

Solution (Python):




import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    
    
    
    ss=readline().rstrip()
    tt=readline().rstrip()

    ls=len(ss)
    lt=len(tt)
    ans=0
    for i in range(0,ls-lt+1):
        n=0
        for j in range(lt):
            if tt[j]==ss[i+j]:
                n+=1
        ans=max(ans,n)
    print(lt-ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

Solution (Python):
s = list(str(input()))
t = list(str(input()))
col = []
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
	col.append(count)
print(len(t)-max(col))

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

res = 10**10

for n in range(len(s)-len(t)+1):
    id = n
    ct = 0
    for k in range(len(t)):
        a = t[k]
        b = s[id]
        if a != b:
            ct += 1
        id += 1
    res = min(res, ct)

print(res)

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

def get_times(head,s,t):
    count = 0
    for i,j in enumerate(range(head,lt+head)):
        if s[j]!=t[i]:
            count+=1
    return count

ans=100000000000000
for i in range(ls-lt+1):
    ans=min(ans,get_times(i,s,t))
print(ans)

Solution (Python):
S=input()
T=input()
cnt=[]
if len(S)==len(T):
    kazu=0
    for i in range(len(S)):
        if S[i]!=T[i]:
            kazu+=1
    cnt.append(kazu)


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

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

ans = float('inf')
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, t - cnt)

print(ans)

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


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

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

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

ans = len(T) - temp_ans
print(ans)

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

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


ans = 10000
for si in range(len(S)-len(T)+1):
    ic = 0
    for ti in range(len(T)):
        if S[si+ti] != T[ti]:
            ic += 1
    ans = min(ic, ans)
        
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline

s = input()[:-1]
t = input()[:-1]

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

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

Solution (Python):
import sys
import math


sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

S = input()
T = input()

ans = 0
for i in range(len(S)):
    for j in range(i+1,len(S)+1):
        if (j-i) == len(T):
            match = 0
            for k,l in enumerate(range(i,j)):
                if S[l] == T[k]:
                    match += 1
            ans = max(ans,match)

print(len(T)-ans)

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

len_s = len(s)
len_t = len(t)
best_score = 0
for i in range(len_s-len_t+1):
    obj = s[i:i+len_t]
    score = 0
    for j in range(len_t):
        if obj[j] == t[j]:
            score += 1
    if score > best_score:
        best_score = score
        
print(len_t - best_score)

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

from collections import defaultdict



def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))



def diff(S, i, T):
    res = 0
    for j in range(len(T)):
        if S[i + j] != T[j]:
            res += 1
    return res

def solve():
    S = input().rstrip()
    T = input().rstrip()
    res = 10 ** 9
    for i in range(0, len(S)):
        if i + len(T) - 1 >= len(S):
            continue
        res = min(res, diff(S, i, T))
    return res

    

if len(sys.argv) > 1 and sys.argv[1].startswith("input"):
    f = open("./" + sys.argv[1], 'r')
    input = f.readline

res = solve()
print(str(res))

Solution (Python):
def solve():
    s = input()
    t = input()
    hoge = 10000
    let = len(t)
    les = len(s)
    ans = 10000
    for i in range(les-let+1):
        hoge = s[i:i+let]
        piyo = 0
        for j, k in zip(hoge,t):
            if j != k:
                piyo += 1
        if piyo < ans:
            ans = piyo
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

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

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

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

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

s = len(S)
t = len(T)
a = s-t+1
ans = t

for i in range(a) :
    x = t
    for j in range(t) :
        if S[i+j] == T[j] :
            x -= 1
    ans = min(ans,x)

print(ans)

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

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

score = [0]*ls

for i in range(ls-lt+1):
    for j in range(lt):
        if t[j] == s[i+j]:
            score[i] += 1

print(lt-max(score))

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

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

max_cnt = 0
for i in range(len(s)-len(t)+1):
    ss = s[i:i+len(t)]
    cnt = 0
    for j in range(len(t)):
        if t[j]==ss[j]:
            cnt += 1
    if max_cnt < cnt:
        max_cnt = cnt

print(len(t)-max_cnt)

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

Solution (Python):
def li():
    return [int(x) for x in input().split()]

S = input()
T = input()

diffs = []

for i in range(len(S)-len(T)+1):
    s = ''
    for j in range(len(T)):
        s += S[i+j]
    diff = 0
    for k in range(len(s)):
        if s[k] != T[k]:
            diff += 1
    diffs.append(diff)

print(min(diffs))

Solution (Python):

import sys


def solve(S: str, T: str):
    def diff(si):
        d = 0
        for i, t in enumerate(T):
            d += S[si+i] != t
        return d
    return min(diff(si) for si in range(0, len(S)-len(T)+1))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  
    T = next(tokens)  
    print(solve(S, T))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()