#include <bits/stdc++.h>
using namespace std;
template <class t>
ostream &operator<<(ostream &tout, const vector<t> &s) {
  tout << '[';
  for (int i = 0; i < s.size(); i++)
    if (i + 1 == s.size())
      tout << s[i];
    else
      tout << s[i] << ',';
  tout << ']';
  return (tout);
}
template <class a, class b>
ostream &operator<<(ostream &tout, const pair<a, b> &c) {
  return (tout << '(' << c.first << ',' << c.second << ')');
}
template <class T>
struct __set__print {
  __set__print(ostream &out) : tout(out), count(0) {}
  void operator()(T x) {
    if (count > 0) tout << ',';
    tout << x;
    ++count;
  }
  ostream &tout;
  int count;
};
template <class T>
ostream &operator<<(ostream &tout, const set<T> &s) {
  tout << '{';
  for_each(s.begin(), s.end(), __set__print<T>(tout));
  return (tout << '}');
}
template <class T, class Q>
struct print_map {
  print_map(ostream &out) : tout(out), count(0) {}
  void operator()(const pair<T, Q> &x) {
    if (count > 0) tout << ',';
    tout << '(' << x.first << " => " << x.second << ')';
    ++count;
  }
  ostream &tout;
  int count;
};
template <class T, class Q>
ostream &operator<<(ostream &tout, map<T, Q> s) {
  tout << '{';
  for_each(s.begin(), s.end(), print_map<T, Q>(tout));
  return (tout << '}');
}
template <class T>
string to_string(T s) {
  stringstream tin;
  tin << s;
  string res;
  getline(tin, res);
  return (res);
}
template <class T>
vector<T> to_vector(T *s, int n) {
  vector<T> result;
  for (int i = 0; i < n; i++) result.push_back(s[i]);
  return (result);
}
const int INF = 1 << 25;
int main() {
  ios_base::sync_with_stdio(false);
  string s, t;
  cin >> s >> t;
  vector<int> dyna(t.size() + 1, 0);
  dyna[0] = 0;
  int ans = 0;
  for (int who = 0; who < s.size(); who++) {
    vector<int> temp(t.size() + 1, 0);
    temp[0] = 0;
    for (int i = 0; i + 1 < dyna.size(); i++)
      temp[i + 1] = max(temp[i + 1], dyna[i] + (s[who] == t[i]));
    ans = max(ans, *max_element(temp.begin(), temp.end()));
    dyna = temp;
  }
  cout << t.size() - ans << endl;
}
