#include <bits/stdc++.h>
using namespace std;
string s, t;
int dp[2005][2005];
int main() {
  memset(dp, 0, sizeof(dp));
  cin >> s >> t;
  int len1 = s.size();
  int len2 = t.size();
  int ans = 0;
  for (int i = len1 - 1; i >= 0; i--) {
    for (int j = len2 - 1; j >= 0; j--) {
      if (s[i] == t[j]) {
        dp[i][j] = 1 + dp[i + 1][j + 1];
        ans = max(ans, 1 + dp[i + 1][j + 1]);
      } else {
        dp[i][j] = dp[i + 1][j + 1];
        ans = max(ans, dp[i + 1][j + 1]);
      }
    }
  }
  cout << len2 - ans << endl;
  return 0;
}
