#include <bits/stdc++.h>
using namespace std;
const int maxn = 2005;
int dp[maxn][maxn];
char a[maxn], b[maxn];
int main() {
  int i, j;
  while (scanf("%s%s", &a, &b) != EOF) {
    int len1 = strlen(a);
    int len2 = strlen(b);
    memset(dp, 0, sizeof(dp));
    int ans = 0;
    for (i = 1; i <= len2; i++) {
      for (j = 1; j <= len1; j++) {
        if (a[j - 1] == b[i - 1]) {
          dp[i][j] = dp[i - 1][j - 1] + 1;
          ans = max(ans, dp[i][j]);
        } else
          dp[i][j] = dp[i - 1][j - 1];
      }
    }
    printf("%d\n", len2 - ans);
  }
  return 0;
}
