#include <bits/stdc++.h>
using namespace std;
int main() {
  string a, b;
  cin >> a >> b;
  for (int i = 0; i < 2000; i++) a = " " + a;
  for (int i = 0; i < 2000; i++) a = a + " ";
  int n = a.size();
  int m = b.size();
  int ans = 2e9;
  for (int i = 0; i < n - m; i++) {
    int cur = 0;
    for (int j = 0; j < m; j++) {
      if (a[i + j] != b[j]) cur++;
    }
    ans = min(ans, cur);
  }
  cout << ans;
}
