#include <string>
#include <iostream>
#include <vector>

int main()
{
	std::string tekst;
	std::string zabr_rec;
	std::getline(std::cin, tekst);
	std::getline(std::cin, zabr_rec);
	if(tekst.size() > 200000 || tekst.size() < 1) return 1;
	if(zabr_rec.size() > 10 || zabr_rec.size() < 1) return 1;
    int j = 0; 
    for (int i = 0; i < tekst.size() && j < zabr_rec.size(); i++)
	{
        if (zabr_rec[j] == tekst[i])
		{
            j++;
		}
	}
    if(j == zabr_rec.size())
	{
	    int rows = tekst.size();
	    int cols = zabr_rec.size();
	    std::vector<int> dp;
	    for(int i = 0; i < rows*cols; i++)
	    {
	    	dp.push_back(0);
	    }
	    for (int j = 0; j < cols; j++) 
	    {
	    	if (tekst[0] == zabr_rec[j]) 
	    	{
	    		dp[j * rows] = 1;
	        }
	    }
	    for (int i = 1; i < rows; i++)
	    {
	    	for (int j = 0; j < cols; j++)
	 		{
	    		if (tekst[i] == zabr_rec[j])
	    		{
	    			dp[j * rows + i] = dp[j * rows + (i - 1)] + 1;
	    			if (j != 0) dp[j * rows + i] = std::min(dp[j * rows + i], dp[(j-1) * rows + (i-1)]);
	    		}
	    		else 
	    		{
	    			dp[j * rows + i] = dp[j * rows + (i-1)];
	    		}
	    	}
	    }
	    std::cout << dp[(cols - 1) * rows + (rows -1)] << std::endl;
	}
	return 0;
}