#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-15, PI = acos(-1);
const int MOD = int(1e9) + 7, MX = int(1e5) + 1;
const int N = 2010;
int memo[N][N];
string a, b;
int ED() {
  int n = int(a.size()), m = int(b.size());
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (a[i - 1] == b[j - 1])
        memo[i][j] = 1 + memo[i - 1][j - 1];
      else
        memo[i][j] = memo[i - 1][j - 1];
  int mn = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) mn = max(mn, memo[i][j]);
  return m - mn;
}
void solve() {
  cin >> a >> b;
  printf("%d\n", ED());
}
int main() { solve(); }
