#include <bits/stdc++.h>
using namespace std;
char haystack[2005 * 5];
char needle[2005];
int main() {
  char buf[2005];
  scanf("%s %s", buf, needle);
  memset(haystack, '#', 2005);
  strcpy(haystack + 2005, buf);
  memset(haystack + 2005 + strlen(buf), '#', 2005);
  int n = strlen(haystack);
  int m = strlen(needle);
  int res = 2005;
  for (int i = 0; i <= n - m; ++i) {
    int cur = 0;
    for (int j = 0; j < m; ++j) {
      if (haystack[i + j] != needle[j]) ++cur;
    }
    res = min(cur, res);
  }
  printf("%d", res);
  return 0;
}
