// Program written by Liu Zhaozhou ~~~
#include <bits/stdc++.h>

#define lowbit(x) x & -x
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast,inline")

using namespace std;

namespace Base {
	inline char gc(void)
	{
		static char buf[100000], *p1 = buf, *p2 = buf;
		return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
	}

	#define gc() getchar()

	template <class T> inline void read(T &x)
	{
		T flag = (T) 1; x = 0; static char ch = gc();
		for (; ch > '9' || ch < '0'; ch = gc())
			flag = ch == '-' ? -1 : 1;
		for (; ch >= '0' && ch <= '9'; ch = gc())
			x = (x << 1) + (x << 3) + (ch & 15);
		x *= flag; return;
	}

	inline void readstr(string&x) {
		x = ""; static char ch;
		while (isspace(ch = gc()));
		while (x += ch, !isspace(ch = gc()));
	}

	inline void readstr(char *s) {
		do *s = gc(); while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
		do *(++s) = gc(); while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
		*s = 0; return;
	}

	inline void printstr(string x, int num = 0, char ch = '\n') {
		for (int i = num; i < x.size(); ++i)
			putchar(x[i]); putchar(ch);
	}

	inline void readch(char&x) { while (isspace(x = gc())); }

	char pf[100000], *o1 = pf, *o2 = pf + 100000;
	#define ot(x) (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf) ++= x : *o1 ++= x)
	template <class T>
	inline void println(T x, char c = '\n') {
		if (x < 0) ot(45), x = -x;
		static char s[15], *b; b = s;
		if (!x) *b ++= 48;
		for (; x; * b ++= x % 10 + 48, x /= 10);
		for (; b-- != s; ot(*b)); ot(c);
	}

	template <class T> inline void write(T x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0'); return;
	}

	template <class T> inline void writeln(T x) { write(x); puts(""); }
	template <class T> inline void writeln(T x, char c) { write(x); putchar(c); }
	template <class T> inline void writeln(char c, T x) { putchar(c); write(x); }

	template <class T> inline void chkmax(T &x, const T y) { x > y ? x = x : x = y; }
	template <class T> inline void chkmin(T &x, const T y) { x < y ? x = x : x = y; }
	template <class T> inline T max(const T&x, const T&y, const T&z) {
		return x > y ? (x > z ? x : z) : (y > z ? y : z);
	}

	typedef long long ll;
	typedef unsigned long long ull;
	typedef long double ld;

	#define Ms(arr, opt) memset(arr, opt, sizeof(arr))
	#define Mc(arr, opt) memcpy(arr, opt, sizeof(opt))
	#define Mp(x, y) make_pair(x, y)

	inline void file(string str) {
		freopen((str + ".in").c_str(), "r", stdin);
		freopen((str + ".out").c_str(), "w", stdout);
	}

	struct Vector {
		double x, y;
		Vector(double _x = 0, double _y = 0) : x(_x), y(_y) {}

		inline Vector Vary(void) { return Vector(x, -y); }

		inline bool operator < (const Vector&rhs)
		const { return x == rhs.x ? y < rhs.y : x < rhs.x; }
		inline Vector operator - (const Vector&rhs)
		const { return Vector(x - rhs.x, y - rhs.y); }
		inline Vector operator + (const Vector&rhs)
		const { return Vector(x + rhs.x, y + rhs.y); }

		inline Vector operator * (const double&rhs)
		const { return Vector(x * rhs, y * rhs); }
		inline Vector operator / (const double&rhs)
		const { return Vector(x / rhs, y / rhs); }

		inline Vector operator * (const Vector&rhs)
		const { return Vector(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
	}; typedef Vector Complex;
}

using namespace Base;

const int Maxn = 1005;
int n, m; char a[Maxn], b[Maxn];

signed main(void) {
//	file("");
	readstr(a + 1), readstr(b + 1);
	n = strlen(a + 1), m = strlen(b + 1);
	int ret = INT_MAX;
	for (int i = 1; i <= n - m + 1; i++) {
		int tmp = m;
		for (int j = 1; j <= m; j++) {
			if (a[i + j - 1] == b[j]) --tmp;
		} chkmin(ret, tmp);
	} writeln(ret);
//	fwrite(pf, 1, o1 - pf, stdout);
	return 0;
}

/**/



Measured memory_bytes: 3624