import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner in = new  Scanner(System.in);
        String s1 = in.nextLine();
        String s2 = in.nextLine();
        int maxlen = 0;
        for(int i=0; i<=s2.length()-s1.length(); i++) {
            int count = 0;
            for(int j=0; j<s1.length(); j++) {
                if(s1.charAt(j) == s2.charAt(i+j)) {
                  count++;
                }
            }
            maxlen = Math.max(maxlen, count);
        }
        System.out.println(s1.length() - maxlen);
    }
}

A = input()
B = input()
na,nb = len(A),len(B)
res = []
for i in range(nb-na+1):
    count = 0
    for j in range(na):
        if B[i+j]!=A[j]:
            count += 1
    res.append(count)
print(min(res))

var s1 = readline();
var s2 = readline();

if(s2.indexOf(s1) !== -1){
    print(0);
}
else{
    var c = [];
    for(var i = 0; i < s2.length - s1.length + 1; i++){
        var s11 = s2.slice(0, i) + s1 + s2.slice(i + s1.length);
        c.push(sameCount(s11, s2));
    }
    print(Math.min.apply(this, c));
}

function sameCount (a, b) {
    var count = 0;
    for(var i = 0; i < a.length; i++){
        if(a.charAt(i) == b.charAt(i)){
            count++;
        }
    }
    return a.length - count;
}

import java.util.Scanner;

/*
 * 直接比较已有字符串中不相等的个数即可
 * */
public class MaxSameLen {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String A = scanner.next();
            String B = scanner.next();

            int min = Integer.MAX_VALUE;
//            以A为模式串
            for (int i = 0; i <= B.length() - A.length(); i++) {
                int tmp = 0;
                for (int j = 0; j < A.length(); j++) {
                    if (A.charAt(j) != B.charAt(i + j)) {
                        tmp++;
                    }
                }
//                如果是子串的话，肯定为0
                min = Math.min(min, tmp);
                if (min == 0) {
                    break;
                }
            }
            System.out.println(min);
        }
    }


}
/*
adaabc
aababbc
2



* */

adaabc

aababbc

为什么输出是2？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

python3

def least_different(a,b):
    la = len(a)
    lb = len(b)
    det = lb-la
    count_list = [0 for j in range(det+1)]
    for i in range(la):
        for j in range(det+1):
            if a[i] != b[i+j]:
                count_list[j] +=1
    return min(count_list)

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

}

package 全国统一模拟第三场;

import java.util.Scanner;

public class Main_3 {
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext())
		{
			String str1=sc.next();
			String str2=sc.next();
			Max_diff(str1,str2);
		}
		sc.close();
	}
	public static void Max_diff(String str1,String str2)
	{
		int min_dif=Integer.MAX_VALUE;
		int diff=0;		
		for(int i=0;i<=str2.length()-str1.length();i++)
		{
			diff=diff_num(str1, str2.substring(i,i+str1.length()));
			min_dif=min_dif<diff?min_dif:diff;			
		}
		System.out.println(min_dif);
	}
	
	public static int  diff_char(String str1,String str2,int diff)
	{
		if(diff==0)
		{						
			return diff_num(str1, str2);
		}
		return Math.min(diff_char(str1, str2.substring(0, str2.length()-1),diff-1), diff_char(str1, str2.substring(1, str2.length()), diff-1));
	}
	public static int diff_num(String str1,String str2)
	{
		int res=0;
		for(int i=0;i<str1.length();i++)
		{
			if(str1.charAt(i)!=str2.charAt(i))
				res++;
		}
		return res;
	}
}

def f(a, b):
    a = '0' + a
    b = '0' + b
    la = len(a)
    lb = len(b)
    if la == lb:
        ret = 0
        for i in range(1, la):
            if a[i] == b[i]:
                ret += 1
        return la - 1 - ret
    dp = [[0]*lb for i in range(la)]
    for i in range(1, la):
        for j in range(i, lb-la+i+1):# 这一步很重要
            if a[i] == b[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = dp[i-1][j-1]
    ret = [max(dp[i]) for i in range(la)]
    ret = max(ret)
    return la - 1 - ret
 
if __name__ == '__main__':
    while 1:
        try:
            a = raw_input()
            b = raw_input()
        except:
            break
        print f(a, b)

	//我的思路是：将a和取长度为（a的长度）的b的连续子串作比较，看每次比较的相应位置的不同字符的个数，求最小值



	let a=readline()



	let b=readline()



	let diff=function(a,b){



	let l=a.length



	let num=0



	for(let i=0;i<l;i++){



	if(a[i]!==b[i])num++;



	}



	return num;



	}



	let al=a.length;



	let min=al;



	for(let i=0,bl=b.length;i<=bl-al;i++){



	let r=diff(a,b.slice(i))



	if(min>r)min=r



	}



	print(min)

	#include <iostream>



	#include <stdio.h>



	#include <string.h>



	 



	using namespace std;



	 



	intdo_it(char*a, char*b){



	    intlen_a = strlen(a);



	    intlen_b = strlen(b);



	    intc[64][64]={0};



	    intmax=0;



	    intm,n;



	    for(inti=0;i<=len_b-len_a;i++){



	        intcnt = 0;



	        for(m=0,n=i;m<len_a;m++,n++){



	            if(a[m]==b[n])



	                cnt++;



	        }



	        if(cnt> max)



	            max = cnt;



	    }  



	    returnlen_a - max;



	}



	 



	intmain(){



	    chara[64],b[64];



	    cin >> a >> b;



	    cout << do_it(a,b) << endl;


}