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

fans = 100000000
for i in range(len(s) - len(t) + 1):
    ans = 0
    for j in range(len(t)):
        if (s[i+j] == t[j]):
            pass
        else:
            ans += 1
    fans = min(fans, ans)

print(fans)

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

def solve(a, b):
	l = len(b)
	maxx = -1
	for i in range(len(a)-l+1):
		val = diff(b, a[i:i+len(b)])
		maxx = max(maxx, val)
	return l - maxx

a = input()
b = input()
print(solve(a, b))

Solution (Python):
import difflib as diff
S=input()
T=input()
diff_count=10001
count=10002


def count_diff2(q, a):
    return sum(
        c1 != c2 for c1, c2 in zip(q, a)
    )

if __name__=="__main__":
    for i in range(len(S)-len(T)+1):
        count=count_diff2(S[i:len(T)+i],T)
        if count <= diff_count:
            diff_count=count

print(diff_count)

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

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

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

    len_s = len(s)
    len_t = len(t)

    if len_s == len_t:
        ans = 0
        for i in range(len_s):
            if s[i] != t[i]:
                ans += 1
        print(ans)
    else:
        ans = 1001
        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)


if __name__ == "__main__":
    main()

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

x = len(s)
y = len(t)
list1 = []
for i in range(x-y+1):
    z = s[i:i+y]
    count = 0
    for n in range(y):
        if z[n] == t[n]:
            count += 1
    list1.append(count)

saidai = max(list1)

saisyo = y - saidai

print(saisyo)

Solution (Python):
s = input()
t = input()
s_list = list(s)
t_list = list(t)
compare = []
score = []

if s == t:
    print(0)
else:
    for i in range(len(s) - len(t) + 1):
        compare.append(s[i : i + len(t)])
    
    for v in compare:
        count = 0
        for v1, v2 in zip(list(v), t_list):
            
            if v1 == v2:
                count += 1
        score.append(count)
    print(len(t) - max(score))

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]









s= input()
t = input()
ans = []
for j in range(len(s)-len(t)+1):
    cnt = 0
    moji = s[j:j+len(t)]
    for k in range(len(t)):
        if moji[k] != t[k]:
            cnt += 1
    ans.append(cnt)
print(min(ans))

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

flag=False

m=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
      flag=True
    
  if m==0 or m<cnt:
    m=cnt

print(len(t)-m)

Solution (Python):



s = input()
t = input()
sl = len(s)
tl = len(t)

def cnt(a,b):
    ret = 0
    for i in range(len(a)):
        ret += a[i]!=b[i]
    return ret

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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)


def unite(par, i, j):
    j = get_par(par, j)
    par[j] = get_par(par, i)

def get_par(par, p):
    while par[p] != p:
        p = par[p]
    return par[p]

def resolve():
    s = input()
    t = input()
    ans = 100000
    for i in range(len(s) - len(t) + 1):
        tmp = 0
        for j in range(len(t)):
            if s[i+j] != t[j]:
                tmp += 1
        if tmp < ans:
            ans = tmp

    print(ans)

if __name__ == "__main__":
    resolve()

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

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

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

Solution (Python):

import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop



n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

S = s1()
T = s1()

m = 10**6
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 m > cnt:
        m = cnt

print(m)

Solution (Python):
ans = 1000
hoge = 0

s = input()
t = input()

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

Solution (Python):



import sys
from io import StringIO
import unittest


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

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

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


def resolve():
    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)


if __name__ == "__main__":
    
    resolve()

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

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

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

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

a = ans.index(max(ans))
b = s[a:a+len(t)]
count = 0
for k in range(len(t)):
    if t[k] != b[k]:
        count += 1
print(count)

Solution (Python):
S = input()
T = input()
ans = 0
for i in range(len(S) - len(T) + 1):
  part = S[i:i+len(T)]
  cnt = 0
  for p, t in zip(part, T):
    if p == t:
      cnt = cnt + 1
  if ans < cnt:
    ans = cnt
print(len(T) - ans)

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

print(ans)

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

Solution (Python):
S = input()
T = input()
N = len(T)
y = 0
for i in range(0,len(S)-N+1):
  
  s = S[i:i+N]
  x = 0
  for k in range(0,N):
    if T[k] == s[k]:
      x = x + 1
  if x >= y:
    y = x
print(N-y)

Solution (Python):
s = input()
t = input()
ans = 0
num0, num1 = len(s), len(t)

for i in range(num0-num1+1):
    count = 0
    for j in range(i, num1+i):
        if s[j] == t[j-i]:
            count += 1
    ans = max(count, ans)
print(len(t)-ans)

Solution (Python):
import numpy

S = numpy.array([ord(s) for s in input()])
T = numpy.array([ord(s) for s in input()])

TL = len(T)
SL = len(S)

C = [numpy.count_nonzero(S[i:i + TL] != T) for i in range(SL - TL + 1)]
print(numpy.min(C))

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


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

Solution (Python):
s = input()
t = input()
present_len = 10000
curr_len = 0
s_len = len(s)
t_len = len(t)
t_chars = list(t)
for i in range(0, (s_len - t_len + 1)):
    j = i
    curr_len = 0
    for k in range(t_len):
        if s[j] != t[k]:
            curr_len += 1
        j += 1
    present_len = min(present_len, curr_len)
print(present_len)

Solution (Python):
import sys,os
import math
from fractions import Fraction 
from collections import defaultdict
from random import randint





def linput():
    return list(minput())

def minput():
    return map(int, sys.stdin.readline().strip().split())



s=input()
t=input()

ans=len(t)

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

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

S_count = len(S)
T_count = len(T)
record = []

try_number = S_count - T_count + 1

for i in range(try_number):
	count = 0
	search_word = S[i:i+T_count]
	for i, letter in enumerate(search_word):
		if T[i] == letter:
			count += 1
		else:
			continue
	record.append(count)
print(T_count-max(record))

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

min = len(t)
for s_index in range(len(s) - len(t) + 1):
    different_chars = 0
    for t_index in range(len(t)):
        if s[s_index + t_index] != t[t_index]:
            different_chars += 1
    if min > different_chars:
        min = different_chars
print(min)

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

len_s = len(s)
len_t = len(t)

min_cnt = len_t

for i in range(len_s - len_t + 1):
  tmp_cnt = len_t
  tmp = s[i:i+len_t]
  for ii in range(len_t):
    if tmp[ii] == t[ii]:
      tmp_cnt -= 1

  if min_cnt > tmp_cnt:
    min_cnt = tmp_cnt

print(min_cnt)

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

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

Solution (Python):
import sys

s = input()
t = input()

finalans = 1000000
for i in range(len(s) - len(t) + 1):
    ans = 0
    for j in range(len(t)):
        if (s[i+j] == t[j]):
            pass
        else:
            ans += 1
    finalans = min(finalans, ans)

print(finalans)

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

ans=len(T)

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

print(len(T)-itti)

Solution (Python):
from sys import stdin

def check_str(s,t):
    com = 0
    if len(t) > len(s):
        return 0
    for a,b in zip(s,t):
        if a == b:
            com += 1
    return com

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

    common = 0
    for i in range(len(s)):
        common = max(common, check_str(s[i:],t))

    print(len(t)-common)

    
if __name__ == "__main__":
    main()

Solution (Python):
s=input()
t=input()
a=len(s)
b=len(t)
ans=1001
kari=0
for i in range(0,a-b+1):
    c=s[i:b+i]
    kari=0
    k=0

    for j in range(b):
        if t[j]!=c[j]:
            kari+=1
      
    if ans>kari:
        ans=kari
print(ans)

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

Ans=1000
for i in range(0, len(S)):
    Tmp=0
    if i + len(T) <= len(S):
      for j in range(0, len(T)):
          if S[i+j] != T[j]:
              Tmp += 1
      Ans = min(Ans, Tmp)
print(Ans)

Solution (Python):
import sys
def sol(s,t):
    m = sys.maxsize
    for i in range(len(s)-len(t)+1):
        c = 0
        for j in range(i,i+len(t)):
            if t[j-i]!=s[j]:
                c+=1
        m = min(m,c)
    print(m)
s = input()
t = input()
sol(s,t)

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

maxS = 0
if len(s) != len(t):
    for i in range(len(s) - len(t)):
        simC = 0
        subS = s[i:i + len(t)]
        for ind,j in enumerate(subS):
            if t[ind] == j:
                simC += 1
        if simC>maxS:
            maxS = simC
    print(len(t) - maxS)
else:
    cou = 0
    for i in range(len(s)):
        if s[i] == t[i]:
            cou += 1
    print(len(s) - cou)

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

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

t_cnt = 0
t_cnt_max = 0
start_pos = 0



for i in range(len(S_list) - len(T_list)+1):
    t_cnt = 0
    for j in range(len(T_list)):
        if S_list[i+j] == T_list[j]:
            t_cnt += 1
            start_pos = i
            
            if t_cnt_max < t_cnt:
                t_cnt_max = t_cnt
print(len(T_list) - t_cnt_max)

Solution (Python):
S = str(input())
T = str(input())
slen = len(S)
tlen = len(T)
ccount = 0
mincount = tlen
for i in range(slen - tlen + 1):
  s = S[i:i + tlen]
  ccount = 0
  for j in range(tlen):
    if T[j] != s[j]:
      ccount += 1
  if ccount <= mincount:
    mincount = ccount
print(mincount)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    S_ = S()
    T = S()
    a = len(S_)
    b = len(T)
    cnt_list = []

    for i in range(a - b + 1):
        cnt = 0
        S_1 = S_[i:i + b]
        for j in range(b):
            if S_1[j] == T[j]:
                cnt += 1
        cnt_list.append(cnt)

    ans = b - max(cnt_list)
    print(ans)



if __name__ == "__main__":
    main()

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

ans =len(t) - res
print(ans)

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

lent = len(T)
ans = lent
for i in range(len(S)-lent+1):
    s = S[i:i+lent]
    lev = 0
    lev = sum(map(lambda x: x[0] != x[1], zip(s, T)))
    if lev == 0:
        ans = 0
        break
    elif lev < ans:
        ans = lev
print(ans)

Solution (Python):
import math
import sys,collections
from sys import stdin, stdout  


def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_string(): return sys.stdin.readline().strip() 
def input(): return sys.stdin.readline().strip()

def file():
	sys.stdin = open('input.py', 'r')
	sys.stdout = open('output.py', 'w') 
def is_subsequence(x, y):
    """Test whether x is a subsequence of y"""
    x = list(x)
    for letter in y:
        if x and x[0] == letter:
            x.pop(0)

    return not x    
def sieve(): 
	spf[1] = 1
	for i in range(2, MAXN): 
		spf[i] = i 
	for i in range(4, MAXN, 2): 
		spf[i] = 2

	for i in range(3, mt.ceil(mt.sqrt(MAXN))): 
		if (spf[i] == i): 
			for j in range(i * i, MAXN, i): 
				if (spf[j] == j): 
					spf[j] = i 
def getFactorization(x): 
	ret = list() 
	while (x != 1): 
		ret.append(spf[x]) 
		x = x // spf[x] 

	return ret 
def getFloor(A, x):

    (left, right) = (0, len(A) - 1)

    ind,floor = -1,-1
    while left <= right:
        mid = (left + right) // 2
        '''if A[mid] == x:
            return mid'''
        if x < A[mid]:
            right = mid - 1
        else:
            floor = A[mid]
            ind=mid
            left = mid + 1
            
    return ind
def check(st) : 
  
    
    n = len(st) 
    digitSum = 0
      
    for i in range(0,n) : 
        digitSum = digitSum + (int)(st[i]) 
  
    
    
    return (digitSum % 9 == 0)     
def isPowerOfTwo(n): 
    if (n == 0): 
        return False
    while (n != 1): 
            if (n % 2 != 0): 
                return False
            n = n // 2
            
              
    return True
def kitte(n):
	c=0
	while(n!=0):
		n=n//2
		c+=1
	return c	
def aa(b,c):
	m=min(b,c)
	b-=m
	c-=m
	if(c>0 and b>0):
		return(m+((b+c)//3))
	else:
		return(m)
def bb(a,c):
	m=min(a,c)
	a-=m
	c-=m
	if(c>0 and a>0):
		return(m+((a+c)//3))
	else:
		return(m)
def cc(b,a):
	m=min(b,a)
	b-=m
	a-=m
	if(a>0 and b>0):
		return(m+((b+a)//3))
	else:
		return(m)		


mod=(10**9)+7	
def main():
	s=input()
	t=input()
	m=float('inf')
	ans=[]
	for i in range(len(s)-len(t)+1):
		c=0
		ind=i
		for j in range(len(t)):
			
			if(s[ind]==t[j]):
				c+=1
			ind+=1	
		
		ans.append(c)
	print(len(t)-max(ans))	


	



	

	
			


		




		






		







			



	

	




	





















	




















		
			


		

			

		





			

	























				

	















	

	










if __name__ == '__main__':
    main()

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

ans = len(s)

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

print(ans)

Solution (Python):
if __name__ == "__main__":
    s = input()
    t = input()
    min_dist = len(s)

    for start in range(len(s) - len(t) + 1):
        curr_dist = 0
        for curr in range(len(t)):
            if s[start + curr] != t[curr]:
                curr_dist += 1
        min_dist = min(min_dist, curr_dist)
    print(min_dist)

Solution (Python):
s=input()
t=input()
ans=float('inf')

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

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

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

print(tt-nax)

Solution (Python):

S = input()
T = input()

last = len(S) - len(T) + 1
ans = len(T)

for i in range(last):
    tent = 0
    for j in range(len(T)):
        if(S[i+j] != T[j]):
            tent += 1
    if(tent < ans):
        ans = tent
print(ans)

Solution (Python):
S = [i for i in input()]
T = [i for i in input()]
N = len(T)
ans = 10**10
for i in range(len(S)-N+1):
     X = S[i:i+N]
     a = N
     for j in range(N):
         if X[j] == T[j]:
             a -= 1
     ans = min(ans, a)
print(ans)

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

cur = 0
count_min = 1000
while cur + len(t) -1 < len(s):
    count = 0
    for i in range(len(t)):
        if t[i] != s[i + cur]:
            count += 1
    if count < count_min:
        count_min = count
    cur += 1
print(count_min)

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

Solution (Python):
i1 = input()
i2 = input()



minNeeded = 99999999999
tt =0 
for i in i1[0:1+(len(i1)-len(i2))]:
  neededChanges = 0
  t = 0
  for ii in i2:
    if ii != i1[tt+t]:
      neededChanges +=1
    t +=1
  if neededChanges < minNeeded:
    minNeeded = neededChanges
  tt += 1
print(minNeeded)

Solution (Python):
def main():
    target = input()
    source = input()
    diff = len(target) - len(source)
    max_change = len(source)
    for i in range(diff+1):
        temp = target[i:len(target)-diff+i]
        change = sum([1 for t, s in zip(temp, source) if(t!=s)])
        if(change < max_change):
            max_change = change
    print(max_change)
if __name__ == '__main__':
    main()

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

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

cnt=0
max=0

for i in range(S-T+1):
    for j in range(T):
        if s[i+j] == t[j]:
            cnt += 1
    else:
        if max<cnt:
            max=cnt
            cnt=0
        else:
            cnt=0

print(T-max)

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

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

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

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

ans = len(T)
for s in range(0, len(S) - len(T) + 1):
    count = 0
    for a, b in zip(S[s:s+len(T)], T):
        if a != b:
            count += 1
    ans = min(ans, count)
print(ans)

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

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

Solution (Python):


S = input()
T = input()

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

print(ans)

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

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

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

len_T = len(T)
min_count = len_T

for i in range(len(S)-len_T+1):

  temp =len_T
  for j in range(len_T):
    if(S[i+j]==T[j]):
      temp-=1
  if(temp ==0):
    print(0)
    sys.exit()
  if(temp<min_count):
    min_count=temp
    
print(min_count)

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

count_all=[]
for i in range(len(S)-len(T)+1):
    count=0
    for j in range(len(T)):
        if S[j+i]!=T[j]:
            count+=1
    else:
        count_all.append(count)

print(min(count_all))

Solution (Python):

S = input()
T = input()

ans = 0
length = len(T)
slen= len(S)
mincnt = 10000
for i in range(slen-length+1):
    tmp = S[i:i+length]
    cnt = 0
    for i in range(length):
        if tmp[i]!=T[i]:
            cnt+=1
    if cnt < mincnt:
        mincnt=cnt
print(mincnt)

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

def f(s,t):
    count = 0
    for i,j in zip(s,t):
        if i == j:
            count += 1
    return count

def F(S,T):
    len_s = len(S)
    len_t = len(T)
    max = 0
    for i in range(len_t,len_s+1):
        x = f(S[i-len_t:i],T)
        if x > max:
            max = x
    return len_t - max
print(F(S,T))

Solution (Python):
S = input()
T = input()
s1 = list(S)
t1 = list(T)
a = len(s1); b = len(t1)
z = []
for i in range(a-b+1):
    x = []
    y = 0
    for j in range(b):
        x.append(s1[i+j])
    for k in range(b):
        if t1[k]==x[k]:
            y += 1
    z.append(y)
print(b-max(z))

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

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

ans=0
for i in range(n-m+1):
    tmp=0
    for j in range(m):
        p=s[i+j]
        q=t[j]
        if s[i+j]==t[j]:
            tmp+=1
    
    ans=max(ans,tmp)

print(m-ans)

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

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

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

sl = len(s)
tl = len(t)
count = 0
for i in range(0,sl-tl+1):
    sb = s[i:i+tl]

    co = 0
    for j in range(tl):

        
        if sb[j] == t[j]:
            co += 1
    if co > count:
        count = co


print(tl - count)

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

s = input()
t = input()

S = len(s)
T = len(t)
ans = int(1e9)
for i in range(S - T + 1):
    mn = T
    for j, k in enumerate(range(T)):
        if s[i+k] == t[j]:
            mn -= 1
    ans = min(mn, ans)


print(ans)

Solution (Python):
s=list(input())
t=list(input())
ans=100000
for i in range(len(s)-len(t)+1):
    cnt=0
    si=s[i:i+len(t)]

    for k in range(len(t)):
        if si[k]==t[k]:
            cnt+=1
    ans=min(ans,len(t)-cnt)
print(ans)

Solution (Python):
s=input()
t=input()
lens=len(s)
lent=len(t)
maxg=0
for i in range(lens-lent+1):
  x=s[i:i+lent]
  g=0
  for j in range(lent):
    if x[j]==t[j]:
      g+=1
  if g>maxg:
    maxg=g
print(lent-maxg)

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

s_len = len(s)
t_len = len(t)
count = 0
c_min = 1000

for i in range(s_len - t_len + 1):
    count = 0
    for j in range(t_len):
        if s[i + j] == t[j]:
            continue
        count += 1
    if c_min > count:
        c_min = count

print(c_min)

Solution (Python):
S = input()
T = input()
D = []
for i in range(len(S) - len(T) + 1):
    SS = S[i:i+len(T)]
    dif = 0
    for j in range(len(T)):
        if T[j] != SS[j]:
            dif += 1
    D += [dif]
            
print(min(D))

Solution (Python):


S = input()
T = input()

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

print(match)

Solution (Python):
S = input()
T = input()
ans = float('inf')
d = len(S) - len(T) + 1

for i in range(d):
  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()
n=len(s)
k=len(t)
ans=10**18
for i in range(n-k+1):
    cnt=0
    for j in range(i,i+k):
        if s[j]!=t[j-i]:
            cnt+=1
    ans=min(ans,cnt)
print(ans)

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

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

ans = n
for i in range(m - n + 1):
    d = 0
    for j in range(n):
        if S[i + j] != T[j]:
            d += 1
    if ans > d:
        ans = d
print(ans)

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

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

print(len(T) - max(A))