#include <bits/stdc++.h>
using namespace std;
int main() {
  string s, t;
  cin >> s >> t;
  s = string(2005, '.') + s + string(2005, '.');
  int n = s.size();
  int m = t.size();
  int ans = 1e9, cur;
  int aux[30];
  for (int i = 0; i < n; i++) {
    cur = 0;
    for (int j = 0; j < m; j++)
      if (s[i + j] == t[j]) cur++;
    ans = min(m - cur, ans);
  }
  cout << ans << endl;
}
