#include <bits/stdc++.h>
using std::bitset;
using namespace std;
int dp[2015][2015] = {0};
int main() {
  char s1[2015] = {0};
  char s2[2015] = {0};
  s1[0] = s2[0] = 'a';
  scanf("%s%s", s1 + 1, s2 + 1);
  int les1 = (int)strlen(s1) - 1;
  int les2 = (int)strlen(s2) - 1;
  int ans = 0;
  for (int i = 1; i <= les1; i++) {
    for (int j = 1; j <= les2; j++) {
      dp[i][j] = dp[i - 1][j - 1] + (s1[i] == s2[j]);
      ans = ans > dp[i][j] ? ans : dp[i][j];
    }
  }
  printf("%d\n", les2 - ans);
  return 0;
}
