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()
length_t = len(t)
counts = []
for i in range(len(s)-len(t)+1):
    tmp_s = s[i:i+length_t]
    counts.append(sum([False if tmp_s[j] == t[j] else True for j in range(length_t)]))
print(min(counts))

Solution (Python):
s=input()
t=input()
n=len(s)-len(t)-1
ans=len(t)
if n==-1:
    cnt=0
    for i in range(len(s)):
        if s[i]!=t[i]:
            cnt+=1
    ans=cnt
else:
    for i in range(n):
        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()
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
  if ans>count:
    ans=count
print(ans)

Solution (Python):
S = input()
T = input()
S1 = list(S)
T1 = list(T)
a = 0
b = 0

for i in range(len(S1)-len(T1)+1):
    if i == 0:
        for j in range(len(T1)):
            if S1[j] != T1[j]:
                a = a + 1
    else:
        for j in range(len(T1)):
            if S1[j+i] != T1[j]:
                b = b + 1
        if b < a:
            a = b
    b = 0

print(a)

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

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
    lists.append(ans)

print(len(t)-max(lists))

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

count = []
for i in range(len(S) - len(T) + 1):
    match_count = 0
    for s, t in zip(S[i:i+len(T)], T):
        if s in t:
            match_count += 1
    count.append(match_count)

print(len(T) - max(count))

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

roop_count = len(s) - len(t) + 1
score = -1

for i in range(roop_count):
    match = 0
    for j,v in enumerate(s[i:len(t)+i]):
        if t[j] == v:
            match += 1
    if match > score:
        score = match

print(len(t) - score)

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


ans = len(t)


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

    ans = min(ans, dif)

print(ans)

Solution (Python):
S, T = input(), input()
rewrite_num = float('inf')
for i in range(len(S) - len(T) + 1):
    
    t = len(list(filter(lambda x: x[0] != x[1], zip(S[i:i+len(T)+1], T))))
    rewrite_num = t if t < rewrite_num else rewrite_num
    
print(rewrite_num)

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

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

ans=0

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

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

difArr = []

for i in range(len(s) - len(t) + 1):
  difCount = 0
  for j in range(len(t)):
    if not(s[i + j] == t[j]):
      difCount += 1
  difArr.append(difCount)

print(min(difArr))

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

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

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

    ans= max(count,ans )

print(lent-ans)

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

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

counter = 0
for i in range(len(S)):
    second = 0
    group = S[i:i+len(T)]
    if len(group) < len(T):
        break
    for j in range(len(T)):
        if T[j] != group[j]:
            second += 1
    if counter == 0:
        counter = second
    elif second < counter:
        counter = second


print(counter)

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

counter = 0
for i in range(len(S)):
    second = 0
    group = S[i:i+len(T)]
    if len(group) < len(T):
        break
    for j in range(len(T)):
        if T[j] != group[j]:
            second += 1
    if counter == 0:
        counter = second
    elif second < counter:
        counter = second


print(counter)

Solution (Python):




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


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


ns = len(s)
nt = len(t)
mn = nt
for i in range(ns-nt+1):
    samenum = sameNum(s[i:i+nt], t)
    mn = min(mn, nt-samenum)
print(mn)

Solution (Python):
S = input()
T = input()
count = 0
max = 0
for j in range(len(T)):
  if T[j] == S[j]:
    count += 1
  if max < count:
    max = count

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

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

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

lst_of_values = []
for i in range(len(S)):
    current = 0
    if i + len(T) > len(S):
        break

    k = 0
    for j in range(i, i+len(T)):
        if S[j] != T[k]:
            current += 1
        k+=1
    lst_of_values.append(current)
    k=0

print(min(lst_of_values))

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[i+j] == T[j]:
            count += 1
    max_count = max(max_count, count)
print(len(T) - max_count)

Solution (Python):
def chk_str(s,t):
    cnt = 0
    for i in range(len(s)):
        if s[i]!=t[i]:
            cnt += 1
    return cnt

s = str(input())
t = str(input())

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

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

ans=10000

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

print(ans)

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

lst_of_values = []
for i in range(len(S)):
    current = 0
    if i + len(T) > len(S):
        break
    for j in range(i, i+len(T)):
        if S[j] != T[j-i]:
            current += 1
    lst_of_values.append(current)

print(min(lst_of_values))

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

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

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

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

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


s_len = len(s)
t_len = len(t)
ans = s_len
for i in range(0,s_len):
    if i+t_len > s_len:
        continue
    tmp = 0
    for j in range(0,t_len):
        if s[i+j] != t[j]:
            tmp = tmp + 1
    ans = min(tmp,ans)

print(ans)

Solution (Python):
s = input()
t = input()
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):
def func(S,T):
  tlen = len(T)
  min = 1000
  for x in range(0,len(S)-tlen+1,1):
    tmp = S[x:x+tlen]
    tmpNum = 0
    for i in range(0,len(tmp),1):
      if tmp[i] != T[i]:
        tmpNum += 1
    if min > tmpNum:
      min = tmpNum
  return min

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

Solution (Python):
s = input()
t = input()
k = len(t)-1

cnt = 9999999

for i in range((len(s)-k)+1):

    if i == 0:
        continue

    Q = s[i-1:i+k]
    x = 0
    for j in range(len(t)):
        x += Q[j] != t[j]
    cnt = min(cnt,x)

print(cnt)

Solution (Python):
def main():
    s=input()
    t=input()
    len_t=len(t)
    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)
    
if __name__ == "__main__":
    main()

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

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

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

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

Solution (Python):


s = input()
t = input()
answer = 0
for start_i in range(len(s)-len(t)+1):
  compared_s = s[start_i:]
  index = 0
  matched_count = 0
  for t_s in t:
    if t_s == compared_s[index]:
      matched_count += 1
    index += 1
  if answer < matched_count:
    answer = matched_count

print(len(t)-answer)

Solution (Python):

S = str(input())
T = str(input())

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

max_match_count = 0

if T in S:
    print(0)
else:
    for i in range(S_len - T_len + 1):
        match_count = 0
        for j in range(T_len):
            if S[i+j:i+j+1] == T[j:j+1]:
                match_count += 1
                max_match_count = max(max_match_count,match_count)

    print(T_len - max_match_count)

Solution (Python):
s = input()
len_s  = len(s)
t = input()
len_t = len(t)
q = []
for i in range(len_s - len_t + 1):
    s2 = s[i:i+len_t]
    n = 0
    for j in range(len_t):
        if t[j] != s2[j]:
            n += 1
    q.append(n)
print(min(q))

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

s=input()
t=input()

cnt=1000
for i in range(len(s)-len(t)+1):  
    cnt = min(cnt,hikaku(s[i:i+len(t)],t))
 
print(cnt)

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

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

a = len(s)
b = len(t)

ans = []

for i in range((a-b)+1):
    an = 0
    for j in range(b):
        if s[i+j] != t[j]:
            an += 1
            
    ans.append(an)

print(min(ans))

Solution (Python):
S = input()
T = input()
LS = len(S)
LT = len(T)
ans = LS

for n in range(1+LS-LT):
  count = 0
  for s,t in zip(S[n:n+LT],T):
    if s!=t:
      count+=1
  ans = min(ans,count)

print(ans)

Solution (Python):
S = input()
T = input()
A = []

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

print(min(A))

Solution (Python):
def check(s1,s2,n):
  ans=0
  for i in range(n):
    ans=ans+(0 if s1[i]==s2[i] else 1)
  return ans
s=input()
t=input()
o_len=len(s)
d_len=len(t)
ans=d_len
for i in range(o_len-d_len+1):
  case_ans=check(s[i:i+d_len],t,d_len)
  ans=min(ans,case_ans)
print(ans)

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

for i in range(len(s)-len(t)+1):
    tmp = len(t)
    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 = len(T)

for i in range(len(S)-len(T)+1):
  tmp = len(T)
  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 = len(T)

for i in range(len(S)-len(T)+1):
  tmp = len(T)
  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()
lens = len(S)
lent = len(T)
ans = lent
for i in range(lens-lent+1):
    s = S[i:i+lent]
    count = 0
    for j in range(lent):
        if s[j] != T[j]:
            count+= 1
    ans = min(ans, count)
print(ans)

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

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

print(min_change)

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

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

    count = 0
    for j in range(len(T)):
        if T[j] == U[j]:
            count += 1

    count_list.append(count)

print(len(T) - max(count_list))

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

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

Solution (Python):
s = input()
t = input()
c = [];
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
  c.append(a)
print(min(c))

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

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

min_num = 10**18
for i in range(n-m+1):
    
    x = sum(a != b for a, b in zip(S[i:i+m], T))
    min_num = min(min_num, x)

print(min_num)

Solution (Python):

S = input()
T = input()

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

print(ans)

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

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

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

print(t-count)

Solution (Python):
s=input()
t=input()
n=len(s)-len(t)+1
cnt=0
x=[]
for i in range(n):
  for l in range(len(t)):
    if s[i+l]!=t[l]:
      cnt=cnt+1
    else:
      continue
  x.append(cnt)
  cnt=0
print(min(x))

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

l1,l2 = len(S),len(T)

ans = float('inf')

for i in range(l1-l2+1):
  swap = 0
  s = i
  for j in range(l2):
    if S[s]!=T[j]:
      swap += 1
    s += 1
  ans = min(ans, swap)

print(ans)

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

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

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

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

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

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

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

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


def calc_diff(s1, s2):
    c = 0
    for i in range(len_t):
        if s1[i] != s2[i]:
            c += 1
    return c


ans = float('inf')
for i in range(len_s - len_t + 1):
    sub_s = S[i:i + len_t]
    c = calc_diff(sub_s, T)
    ans = min(ans, c)

print(ans)

Solution (Python):

a = input()
b = input()
pointer = 0
smallest  = 0
def compare(s1,s2):
	count = 0
	for x in range(len(s1)):
		if s1[x] == s2[x]:
			count+=1
	return count
for x in range(len(a)- len(b)+1):
	value =  compare(b,(a[x:x+len(b)]))
	smallest = max(value,smallest)
print(len(b) - smallest)

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

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




'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''
s=input().rstrip("\n")
t=input().rstrip("\n")
cnt=[0]*len(s)
if len(s)>len(t):
    for i in range(len(s)-len(t)):
        for j in range(len(t)):
            if t[j]==s[i+j]:
                cnt[i]+=1
else:
    for i in range(len(s)):
        if t[i]==s[i]:
            cnt[0]+=1
print(len(t)-max(cnt))

Solution (Python):
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math


rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

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

def main():
	s, t = rll()[0], rll()[0]
	m = len(t)
	ans = INF 

	def do(start):
		x = 0
		for i in range(m):
			if start + i >= len(s):
				return INF
			if t[i] != s[start + i]: 
				x += 1
		return x

	for i in range(len(s)):
		ans = min(ans, do(i))
	print(ans)

	stdout.close()

if __name__ == "__main__":
	main()

Solution (Python):
s = input()
t = input()
m = len(s)
n = len(t)
did = m -n
li = []
for i in range(did+1):
  su = 0
  for j in range(n):
    if t[j] ==s[i+j]:
      su +=0
    else:
      su +=1
  li.append(su)
print(min(li))

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

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

n_s = len(S)
n_t = len(T)
ans = float('inf')
for i in range(n_s-n_t+1):
    tmp = 0
    for j in range(n_t):
        if S[i+j] != T[j]:
            tmp += 1
    ans = min(ans, tmp)
print(ans)

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

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

Solution (Python):
s_str = input()
t_str = input()
t_len = len(t_str)
roop_num = len(s_str)-t_len+1
max_num = 0
for i in range(roop_num):
    match_str = s_str[i:i+t_len]
    match_num = sum([match_str[j]==t_str[j] for j in range(t_len)])
    if max_num < match_num:
        max_num = match_num
print(t_len-max_num)

Solution (Python):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def NLI(n):return [[int(i) for i in input().split()] for i in range(n)]
def NLI_(n):return [[int(i)-1 for i in input().split()] for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7

inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

ans=0


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

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

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

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

print(ans)

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

Solution (Python):
S=input()
T=input()
list1=[]
for i in range(len(S)-len(T)+1):
  a=S[i:(i+len(T))]
  cnt=0
  for j in range(len(T)):
    if a[j]!=T[j]:
      cnt=cnt+1
  list1.append(cnt)
b=min(list1)
print(b)

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

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

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

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

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())
n=len(s)-len(t)+1
cli=[]
for i in range(n):
  a=[]
  for j in range(i):
    a.append('')
  a.extend(t)
  for j in range(n-1-i):
    a.append('')
  count=0
  for i in range(len(s)):
    if s[i]==a[i]:
      count+=1
  cli.append(count)
print(len(t)-max(cli))

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

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

print(ans)

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

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

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

N = len(T)

s_list = []
for i in range(len(S) - N + 1):
    s = S[i:i + N]
    s_list.append(s)


answer = N  
for s in s_list:
    counter = 0  
    
    for i in range(N):
        if s[i] != T[i]:
            counter += 1
    answer = min(answer, counter)  

print(answer)

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

if t in s:
    print(0)
    exit()

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

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

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


print(mint)

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

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

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

n, m = len(S), len(T)
maximum = 0
for i in range(n - m + 1):
    count = 0
    for j in range(m):
        if S[j + i] == T[j]:
            count += 1
    maximum = max(maximum, count)

ans = m - maximum

print(ans)

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

Solution (Python):
S = input()
T = input()
ans = []

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.append(count)

print(min(ans))

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

cor = 0
ans = 0

for entry in range(len(s)-len(t)+1):
    for i in range(len(t)):
        if s[entry + i] == t[i]:
            cor += 1
    if ans < cor:
        ans = cor
    cor = 0

print(len(t)-ans)

Solution (Python):
p = list(input())
t  = list(input())
count = 0
w =[]
a = len(t)
b = len(p)

for i in range(b-a+1):
    count = 0
    for s in range(a):
        if p[i] != t[s]:
            count +=1
        i +=1
    w.append(count)
print(min(w))

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

ans = 10**9

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

Solution (Python):


if __name__ == "__main__":
    S = input()
    T = input()
    
    result = 999999
    for i in range(len(S)-len(T)+1):
        to_change = 0
        for j in range(len(T)):
            if T[j] != S[i+j]:
                to_change += 1
        result = min(result,to_change)

    print(result)

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

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

print(ans)

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

count = []

for i in range(len(s)-len(t)+1):
    c=0
    for j in range(i,i+len(t)):
        if s[j] == t[j-i]:
            c+=1
    count.append(c)


print(len(t)-max(count))

Solution (Python):
s = input()
t_list = list(input())
ans = len(t_list)

for start in range(len(s) - len(t_list) + 1):
    diff = 0
    for i in range(len(t_list)):
        if(t_list[i] != s[start + i]):
            diff += 1
        
    ans = min(ans, diff)

print(ans)

Solution (Python):


S = input()
T = input()
min_diff_count = float("inf")
for i in range(len(S)):
    if i + len(T) > len(S):
        break
    count = 0
    for j in range(len(T)):
        if S[i + j] != T[j]:
            count += 1
    min_diff_count = min(min_diff_count, count)


ans = min_diff_count
print(ans)

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

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

Solution (Python):
S = list(input())
T = list(input())
ls = len(S)
lt = len(T)
res = 1000
for i in range(ls - lt + 1):
  temp = 0
  for j in range(lt):
    if S[i+j] != T[j]:
      temp += 1
  if res > temp:
    res = temp
print(res)

Solution (Python):
S=str(input())
T=str(input())
if T in S:
    print(0)

else:
    S=list(S)
    T=list(T)
    nums=len(T)
    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
        nums=min(nums,ans)
    print(nums)

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

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

Solution (Python):
import math
S = input()
T = input()
min0 = len(T)


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

print(min0)

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

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

Solution (Python):
s = input()
t = input()
l = []
for i in range(len(s)-len(t) + 1):
    cnt = 0
    w = s[i:i+len(t)]
    for d in range(len(t)):
        if t[d] == w[d]:
            cnt += 1
    l.append(cnt)
print(len(t) - max(l))

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


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

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

print(min_ch)

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

Solution (Python):
S=input()
T=input()
ans=0
for i in range(max(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(len(T)-ans)