#include <bits/stdc++.h>
using namespace std;
const int maxn = 3000;
char second[maxn + 1], t[maxn + 1];
int d[maxn + 1][maxn + 1];
int main() {
  gets(second);
  gets(t);
  int sn = strlen(second);
  int tn = strlen(t);
  for (int i = sn - 1; i >= 0; --i)
    for (int j = tn - 1; j >= 0; --j) {
      d[i][j] = d[i + 1][j + 1] + (second[i] == t[j]);
    }
  int ans = (1 << 30);
  for (int i = 0; i < sn; ++i)
    for (int j = 0; j < tn; ++j) ans = min(ans, tn - d[i][j]);
  cout << ans << endl;
  return 0;
}
