#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <chrono>
#include <string>
using namespace std;
typedef long long ll;

bool word_appears(const string& s, const string& word)
{
	int i = 0;
	for (int j = 0; j < s.size() && i < word.size(); j++)
	{
		if (s[j] == word[i])
		{
			i++;
		}
	}
	return i == word.size();
}

int solve_recurse(string& s, int pos, const string& word)
{
	if (pos == s.size())
	{
		if (word_appears(s, word))
			return 100000;
		else
			return 0;
	}
	int sol1 = solve_recurse(s, pos + 1, word);
	char prev_char = s[pos];
	s[pos] = '*';
	int sol2 = solve_recurse(s, pos + 1, word) + 1;
	s[pos] = prev_char;
	return min(sol1, sol2);
}

int bruteforce(string s, const string& word)
{
	return solve_recurse(s, 0, word);
}

int solve(string& s, const string& word)
{
	vector<vector<int>> dp(word.size(), vector<int>(s.size()));
	vector<vector<pair<int, int>>> prev(word.size(), vector<pair<int, int>>(s.size(), { -1,-1 }));

	dp[0][0] = (s[0] == word[0]);
	prev[0][0] = { -1,-1 };
	for (int i = 1; i < s.size(); i++)
	{
		dp[0][i] = dp[0][i - 1] + (s[i] == word[0]);
		prev[0][i] = { 0,i - 1 };
	}
	
	for (int row = 1; row < word.size(); row++)
	{
		for (int col = row; col < s.size(); col++)
		{
			if (s[col] == word[row])
			{
				int delete_letter = dp[row][col - 1] + 1;
				int keep_letter = dp[row - 1][col - 1];
				if (delete_letter < keep_letter)
				{
					dp[row][col] = delete_letter;
					prev[row][col] = { row,col - 1 };
				}
				else
				{
					dp[row][col] = keep_letter;
					prev[row][col] = { row - 1,col - 1 };
				}
				
			}
			else
			{
				dp[row][col] = dp[row][col - 1];
				prev[row][col] = { row,col - 1 };
			}
		}
	}

	int current_row = word.size()-1, current_col = s.size()-1;
	while (true)
	{
		int prev_row = prev[current_row][current_col].first;
		int prev_col = prev[current_row][current_col].second;
		if (prev_row == -1)
		{
			if (current_row == 0 && current_col == 0 && dp[0][0] == 1)
			{
				s[0] = '*';
			}
			break;
		}

		int prev_value = dp[prev_row][prev_col];
		if (prev_row == current_row && prev_value < dp[current_row][current_col])
		{
			s[current_col] = '*';
		}
		current_row = prev_row;
		current_col = prev_col;
	}


	return dp.back().back();
}

string generate_rand_str(int len)
{
	string s(len, ' ');
	for (int i = 0; i < len; i++)
	{
		s[i] = 'a' + rand() % 26;
	}
	return s;
}

void test(double frac)
{
	int s_len = rand() % 10 + 1;
	int w_len = rand() % 10 + 1;
	string s = generate_rand_str(s_len);
	string start_s = s;
	string w = generate_rand_str(w_len);
	int sol1 = bruteforce(s, w);
	int sol2 = solve(s, w);
	if (sol1 != sol2)
	{
		cout << "wa\n";
		cout << start_s << "\n" << w << "\n";
		solve(start_s, w);
	}
	else if (word_appears(s, w))
	{
		cout << "wa incorrect removal\n";
		cout << start_s << "\n" << w << "\n";
		solve(start_s, w);
	}
	else
	{
		cout << fixed;
		cout << setprecision(5);
		cout << frac << "%\r";
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	srand(time(0));

	string s, word;
	cin >> s >> word;
	//cout << bruteforce(s, word) << "\n";
	cout << solve(s, word) << "\n";
	cout << s << "\n";
	
	/*int test_cnt = 10000000;
	for (int i = 0; i < test_cnt; i++)
	{
		double frac = i * 1.0 / test_cnt;
		test(frac*100);
	}
	cout << "done\n";*/

	return 0;
}