#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define boAshraf { ios_base::sync_with_stdio(false); cin.tie(NULL); }
#define ll long long
#define sz(s) (int)(s).size()
#define endl "\n"
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

void File();
void sol();
int f[(int)1e5+5];
void KMP(const string&pat){
int len = 0;
f[0] = 0;
for (int i = 1; i < pat.size(); ++i) {
while (len>0 && pat[i] != pat[len])
len = f[len - 1];
if (pat[i] == pat[len])
++len;
f[i] = len;
}
}
vector<vector<int>>aut;
void compute_automaton(string s) {
s += '#';
int n = s.size();
aut.assign(n, vector<int>(27));
for (int i = 0; i < n; i++) {
for (int c = 0; c < 26; c++) {
if (i > 0 && 'a' + c != s[i])
aut[i][c] = aut[f[i - 1]][c];
else
aut[i][c] = i + ('a' + c == s[i]);
aut[i][26]=max(aut[i][c],aut[i][26]);
}
}
}
string pat,s;
const int N=1e4,M=1e3;
int n,m;
int idd;
int dp[N][M];
int vis[N][M];
int rec(int i,int match){
if(match==m)return 1e9;
if(i==n)return 0;
int &ret=dp[i][match];
if(vis[i][match]==idd)return ret;
vis[i][match]=idd;
ret=1e9;
if(s[i]==pat[match]){
ret=min(rec(i+1,match)+1,rec(i+1,match+1));
}
int sz=aut[match][s[i]-'a'];
ret= min(ret,rec(i+1,sz));
return ret;
}
int main() {
boAshraf
File();
int t = 1;
//cin >> t;
while (t--) {
sol();
}
return 0;
}
void sol() {
while(cin>>s>>pat){
KMP(pat);
compute_automaton(pat);
n=s.size();m=pat.size();
++idd;
cout<<rec(0,0)<<endl;
}
}

void File() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}