#include <stdio.h>
#include <string.h>
#define INFILE    "subsir.in"
#define OUTFILE   "subsir.out"
#define MAXLEN	   1001
#define INFTY	   10000

char A[MAXLEN+1], B[MAXLEN+1];
int T[MAXLEN+1][MAXLEN+1];
int len1, len2, ultap[MAXLEN]['z'-'a'+1];
/* ultap[i][j] este pozitia ultimei aparitii a literei j+'a'
   in prefixul de lungime i al lui B */
/*T[i][j]==lungimea celui mai scurt subsir din A[0..i] care nu este subsir al lui
  B[0..j] */

void load_data ( void )
{FILE *f=fopen (INFILE, "rt");
 fscanf (f, "%s%s", A, B);
 fclose (f); }

void recursiv (int i, int j)
{
/* dinamica */
if (T[i][j]) return;
if (j==0)
   {  T[i][0]=1;  return;   }
if (i==0)
   {
   if (ultap[j][A[0]-'a']==0)  /* prima litera din A nu apare in prefixul de lungime j al lui B */
	  { T[0][j]=1; return;	  }
	  else
	  { T[0][j]=INFTY; return;  }
   }
if (ultap[j][A[i]-'a'] == 0)
   {T[i][j]=1; return;  }
recursiv(i-1, j); recursiv (i-1, ultap[j][A[i]-'a']-1);
if (T[i-1][j] < T[i-1][ultap[j][A[i]-'a']-1]+1)
		T[i][j]=T[i-1][j];
	else
		T[i][j]=T[i-1][ultap[j][A[i]-'a']-1]+1;
}

void solve ( void )
{int i, j;
 len1=strlen (A), len2=strlen (B);
 for (i='a'; i<='z'; i++) ultap[0][i-'a']=0;
 for (i=1; i<=len2; i++)
	 for (j='a'; j<='z'; j++)
	 {
	 ultap[i][j-'a']=ultap[i-1][j-'a'];
	 if (B[i-1]==j)
		{ultap[i][j-'a']=i;}
	}
 recursiv (len1-1, len2);
}

void write_solution ( void )
{FILE *fout=fopen(OUTFILE, "wt");
 fprintf (fout, "%d\n", T[len1-1][len2]);
 fclose (fout);
}

int main ( void )
{
	load_data();
	solve();
	write_solution();
	return 0;
}