#include<cstdio>

#include<cstring>

#define N 1010

char a[10010],b[N];int n,m,i,j,k,x,nxt[N],f[2][N],ans;

inline void up(int&a,int b){if(a<b)a=b;}

int main(){

  scanf("%s%s",a+1,b+1),n=strlen(a+1),m=strlen(b+1);

  for(i=2;i<=m;nxt[i++]=j){

    while(j&&b[j+1]!=b[i])j=nxt[j];

    if(b[j+1]==b[i])j++;

  }

  for(j=1;j<m;j++)f[0][j]=-1;

  for(i=0;i<n;i++,x^=1){

    for(j=0;j<m;j++)f[x^1][j]=-1;

    for(j=0;j<m;j++)if(~f[x][j]){

      up(f[x^1][j],f[x][j]);

      for(k=j;k&&b[k+1]!=a[i+1];k=nxt[k]);

      if(b[k+1]==a[i+1])k++;

      up(f[x^1][k],f[x][j]+1);

    }

  }

  for(j=0;j<m;j++)up(ans,f[x][j]);

  return printf("%d",n-ans),0;

}