#include <bits/stdc++.h>
using namespace std;
char b[2005];
char a[2005];
int dp[2005][2005];
int main() {
  int n, i, j, l1, l2;
  scanf("%s", a);
  scanf("%s", b);
  l1 = strlen(a);
  l2 = strlen(b);
  for (i = 0; i <= l1; i++) dp[i][0] = 0;
  for (i = 0; i <= l2; i++) dp[0][i] = 0;
  int max1 = -100000000;
  for (i = 1; i <= l1; i++) {
    for (j = 1; j <= l2; j++) {
      if (a[i - 1] == b[j - 1])
        dp[i][j] = dp[i - 1][j - 1] + 1;
      else
        dp[i][j] = dp[i - 1][j - 1];
      if (dp[i][j] > max1) max1 = dp[i][j];
    }
  }
  printf("%d\n", l2 - max1);
  return 0;
}
