#include <bits/stdc++.h>
using namespace std;
int res;
int DN[2005][2005];
char S1[2005], S2[2005];
int main() {
  scanf("%s%s", S1 + 1, S2 + 1);
  int uz1 = strlen(S1 + 1);
  int uz2 = strlen(S2 + 1);
  for (int i = 1; i <= uz1; i++)
    for (int j = 1; j <= uz2; j++) {
      DN[i][j] = DN[i - 1][j - 1] + (S1[i] == S2[j]);
      res = max(res, DN[i][j]);
    }
  printf("%d\n", uz2 - res);
  return 0;
}
