#include <bits/stdc++.h>
using namespace std;
int solve(string S, const string& U) {
  string pad(2000, 'Z');
  S = pad + S + pad;
  int best = 2000;
  for (int i = 0; i + U.size() <= S.size(); ++i) {
    int nDif = 0;
    for (int k = 0; k < U.size(); ++k) nDif += (S[i + k] != U[k]);
    best = min(best, nDif);
  }
  return best;
}
int main() {
  for (string S, U; cin >> S >> U;) cout << solve(S, U) << endl;
}
