#include <bits/stdc++.h>
	 
	using namespace std;
	 
	int main() {
		ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	    string t, s;
	    cin >> t >> s;
	    int dp[t.size()][s.size()] = {};
	    for(int i = 0; i < s.size(); i++) if(t[0] == s[i]) dp[0][i] = 1;
	    for(int i = 1; i < t.size(); i++) {
	        for(int j = 0; j < s.size(); j++) {
	            if(t[i] == s[j]) {
	                dp[i][j] = dp[i - 1][j] + 1;
	                if(j != 0) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
	            }
	            else dp[i][j] = dp[i - 1][j];
	        }
	    }
	    cout << dp[t.size() - 1][s.size() - 1] << "\n";
	    return 0;
	}