#include <bits/stdc++.h>
using namespace std;
const int MN = 2e3 + 10;
const int INF = 1e9 + 10;
int n, m;
string s, t;
int same[MN][MN];
void prep() {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      same[i + 1][j + 1] = same[i][j];
      if (s[i] == t[j]) ++same[i + 1][j + 1];
    }
}
int main() {
  cin >> s >> t;
  n = s.size(), m = t.size();
  prep();
  int ans = INF;
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j <= m; ++j) ans = min(ans, m - same[i][j]);
  cout << ans << endl;
  return 0;
}
