#include <bits/stdc++.h>
using namespace std;
stringstream sss;
int main() {
  string s, u;
  cin >> s >> u;
  for (int i = 0; i < 2000; i++) {
    s.insert(s.begin(), '*');
    s.push_back('*');
  }
  int minMatch = (int)1e9;
  for (int i = 0; i < s.length() - u.length(); i++) {
    int currMatch = (int)u.length();
    for (int j = 0; j < u.length(); j++) {
      if (s.at(i + j) == u.at(j)) {
        currMatch--;
      }
    }
    minMatch = min(minMatch, currMatch);
  }
  cout << minMatch;
  return 0;
}
