#include <bits/stdc++.h>
using namespace std;
const int Maxn = 2010;
int dp[Maxn][Maxn];
char s[Maxn], u[Maxn];
int main() {
  scanf("%s%s", s, u);
  int ls = strlen(s);
  int lu = strlen(u);
  int ans = 0;
  for (int i = 1; i <= ls; ++i) {
    for (int j = 1; j <= lu; ++j) {
      dp[i][j] = dp[i - 1][j - 1] + (s[i - 1] == u[j - 1]);
      ans = max(ans, dp[i][j]);
    }
  }
  printf("%d\n", lu - ans);
  return 0;
}
