#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 300;
const int INF = 0x3f3f3f3f;
char s1[maxn * 2], s2[maxn * 2];
int dp[maxn * 2][maxn * 2];
int main() {
  scanf("%s%s", s1 + 1, s2 + 1);
  int len1, len2;
  len1 = strlen(s1 + 1);
  len2 = strlen(s2 + 1);
  int ans = 0;
  for (int i = 1; i <= len1; i++) {
    for (int j = 1; j <= len2; j++) {
      ans = max(ans, dp[i][j] = dp[i - 1][j - 1] + (s1[i] == s2[j]));
    }
  }
  cout << len2 - ans << endl;
  return 0;
}
