#include <bits/stdc++.h>
using namespace std;
const int N = 6005;
char U[N], V[N], T[N];
int n, m;
int main() {
  scanf("%s", T);
  n = strlen(T);
  scanf("%s", V);
  m = strlen(V);
  copy(T, T + n, U + m);
  n += m * 2;
  int res(m), cur;
  for (int i = 0; i + m <= n; ++i) {
    cur = 0;
    for (int j = 0; j < m; ++j) cur += U[i + j] != V[j];
    res = min(res, cur);
  }
  printf("%d\n", res);
}
