#include <bits/stdc++.h>

using namespace std;

#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define          file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }

// end of template

const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1}; // {2, 1, -2, -1, -2, 1, 2, -1, 2};
const int MAX_S = 1e4 + 4;
const int MAX_T = 1e3 + 3;

string S, T;
int kmp[MAX_T], nxt[MAX_T][256], szT, szS;

void init(void) {
	cin >> S >> T;
	szS = S.size(); szT = T.size();
	S = ' ' + S + ' '; T = ' ' + T + ' ';
	REP(j, 26) nxt[0][j] = 0;
	kmp[0] = 0; nxt[0][T[1] - 'a'] = 1;
	FOR(i, 1, szT) {
		kmp[i] = i == 1 ? 0 : nxt[kmp[i - 1]][T[i] - 'a'];
		REP(j, 26) nxt[i][j] = j == T[i + 1] - 'a' ? i + 1 : nxt[kmp[i]][j];
	}
}

int dp[MAX_S][MAX_T];

void process(void) {
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0] = 0;
	REP(i, szS) REP(j, szT) {
		minimize(dp[i + 1][nxt[j][S[i + 1] - 'a']], dp[i][j]);
		minimize(dp[i + 1][j], dp[i][j] + 1);
	}
	int res = szS;
	REP(j, szT) minimize(res, dp[szS][j]);
	cout << res << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("pstring");
	REP(love, 3) {
		init();
		process();
	}
	return (0^0);
}