#include<stdio.h>
#include<string.h>
#define min(a,b) (a>b?b:a)
int dp[110][110],ans[110];
char str1[110],str2[110];
int main()
{
	while(scanf("%s%s",str1+1,str2+1)!=EOF)
	{
		int i,j,k;
		int len=strlen(str1+1);
		memset(dp,0,sizeof(dp));
		memset(ans,0,sizeof(ans));
		for(i=1;i<=len;i++)
			dp[i][i]=1;
		for(i=len-1;i>=1;i--)//a串和b串一个也不相等时
		{
			for(j=i+1;j<=len;j++)
			{
				dp[i][j]=dp[i+1][j]+1;
				for(k=i+1;k<=j;k++)
				{
					if(str2[i]==str2[k])
					{
						dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j]);
					}
				}
			}
		}
		for(i=1;i<=len;i++)
		{
			ans[i]=dp[1][i];
			if(str1[i]==str2[i])
			{
				ans[i]=ans[i-1];
			}
			else
			{
				for(j=1;j<i;j++)
				{
					ans[i]=min(ans[i],ans[j]+dp[j+1][i]);
				}
			}
		}
		printf("%d\n",ans[len]);
	}
}