#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int inf = 1000000000;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	string s1, s2;
	cin >> s1 >> s2;
	
	int l1 = s1.length();
	int l2 = s2.length();
	
	int mem[l1][l2] = {0};
	
	for(int i = 0; i < l1; ++i)
		if(s1[i] == s2[0]) mem[i][0] = 1;
		
	for(int i = 1; i < l1; ++i)
		for(int j = 0; j < l2; ++j)
		{
			if(s1[i] == s2[j])
				mem[i][j] = min(mem[i-1][j]+1, (j == 0 ? inf : mem[i-1][j-1]));
			else
				mem[i][j] = mem[i-1][j];
		}
		
	cout << mem[l1-1][l2-1] <<endl;
	
}