#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define F first
#define S second
#define Lnode 2*node+1
#define Rnode 2*node+2
#define MID (l+r>>1)
#define el '\n'
#define coutf(x) for(auto v:(x)) cout<<v<<' '; cout<<el
#define coutp(x) for(auto v:(x)) cout<<v.F<<' '<<v.S<<el
#define cinl(x) for(auto &v:(x)) cin>>v;
#define all(x)  x.begin(),x.end()
#define ll long long
#define sz(x)  (int)x.size()
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define vi vector<ll>
using ull = unsigned long long;
string x,y;
int n,m;
int idx=1;
vector<ll>pref;

vector<ll>compute(const string& s)
{
    int sz=s.size();
    vector<ll>phi(sz,0);
    for (int i=1,k=0;i<sz;i++){
        k=phi[i-1];
        while (k>0&&s[i]!=s[k])k=phi[k-1];
        if (s[i]==s[k])k++;
        phi[i]=k;
    }
    return phi;
}
const int N=1e4+4,M=1e3+3,oo=1e9;
int dp[N][M],vis[N][M];
int autom[M][26],autovis[M][26];
int next_j(int j,char c)
{
    if (j==0) return (y[0]==c);
    if (y[j]==c)return j+1;
    int &ret=autom[j][c-'a'];
    if (autovis[j][c-'a']==idx)return ret;
    autovis[j][c-'a']=idx;

    return ret=next_j(pref[j-1],c);
}
int kmp(int i,int j){
    if (j>=m)return oo;
    if (i>=n)return 0;
    int &ret=dp[i][j];
    if (vis[i][j]==idx)return ret;
    vis[i][j]=idx;
    ret=oo;
    ret=min(ret,1+kmp(i+1,j));

    j=next_j(j,x[i]);
        ret=min(ret,kmp(i+1,j));

    return ret;
}

void solve()
{
    while(cin>>x>>y)
    {

    n=x.size(),m=y.size();
    pref=compute(y);
    cout<<kmp(0,0);
    idx++;

    }



}




int32_t main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif


    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tc = 1;
    //cin >> tc;
    for (int i = 1; i <= tc; i++){solve();}
    return 0;
}

/*
*/