#include <bits/stdc++.h>
using namespace std;
int static fast = []() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  return 0;
}();
int main() {
  string s, t;
  cin >> s >> t;
  vector<vector<int>> edit(s.size() + 1, vector<int>(t.size() + 1, 0));
  int ans = 0;
  for (int i = 0; i < s.size(); i++) {
    for (int j = 0; j < t.size(); j++) {
      if (s[i] == t[j]) {
        edit[i + 1][j + 1] = edit[i][j] + 1;
      } else {
        edit[i + 1][j + 1] = edit[i][j];
      }
      ans = max(ans, edit[i + 1][j + 1]);
    }
  }
  cout << t.size() - ans << endl;
  return 0;
}
