#include <bits/stdc++.h>
using namespace std;
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  string str1, str2;
  cin >> str1 >> str2;
  long long len1 = str1.length();
  long long len2 = str2.length();
  vector<vector<long long>> dp(len1 + 1, vector<long long>(len2 + 1));
  long long ans = 0;
  for (long long i = 1; i <= len1; i++) {
    for (long long j = 1; j <= len2; j++) {
      dp[i][j] = dp[i - 1][j - 1] + (str1[i - 1] == str2[j - 1]);
      ans = max(ans, dp[i][j]);
    }
  }
  cout << len2 - ans << endl;
}
