#include <bits/stdc++.h>
using namespace std;
double Pi = 2 * asin(1.0);
string a, b;
int d[2005][2005];
int main() {
  int i, j, mx = 0;
  cin >> a;
  cin >> b;
  int na = a.size(), nb = b.size();
  for (i = 1; i <= na; i++) {
    for (j = 1; j <= nb; j++) {
      d[i][j] = d[i - 1][j - 1] + (a[i - 1] == b[j - 1]);
      mx = max(mx, d[i][j]);
    }
  }
  printf("%d\n", nb - mx);
  return 0;
}
