#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, N = 2e3 + 5, MOD = 1e9 + 7;
int T, cas = 0;
int n, m, dp[N][N];
char s[N], u[N];
int main() {
  memset(dp, 0, sizeof(dp));
  scanf("%s", s);
  scanf("%s", u);
  n = strlen(s), m = strlen(u);
  for (int i = 0; i < (n); i++) {
    for (int j = 0; j < (m); j++) {
      if (s[i] == u[j])
        dp[i + 1][j + 1] = dp[i][j] + 1;
      else
        dp[i + 1][j + 1] = dp[i][j];
    }
  }
  int ans = 0;
  for (int i = (0); i <= (n); i++)
    for (int j = (0); j <= (m); j++) ans = max(ans, dp[i][j]);
  printf("%d\n", m - ans);
  return 0;
}
