#include <bits/stdc++.h>
using namespace std;
int dp[2003][2003];
char a[2003], b[2003];
int max(const int &a, const int &b) { return a > b ? a : b; }
int main(void) {
  int la, lb, ans = 0;
  a[0] = b[0] = 1;
  scanf("%s%s", &a[1], &b[1]);
  la = strlen(a);
  lb = strlen(b);
  la--;
  lb--;
  for (int i = 1; i <= la; i++)
    for (int j = 1; j <= lb; j++)
      ans = max(ans, dp[i][j] = dp[i - 1][j - 1] + (a[i] == b[j]));
  printf("%d\n", lb - ans);
  return 0;
}
