// uva live 4394 String painter
//
// 这一题是训练指南上dp专题的习题，初看之下认为仅仅是稍微复杂了一点
// 就敲阿敲阿敲，两个半小时后，发现例子过了。然而自己给出的数据跪了
// 交了也wa了，才发现，自己的方法是有问题的，假设是将两个串同一时候考虑
// 的话，比方: dp[i][j] 表示从i到j，s串刷成目标b串所须要的最小的花费
// 然后依据区间的端点的字符特点，进行状态转移，然而可能是我太搓了，
// 发现这种状态转移是不正确的。比方edc和cde，依照我d方法算出来是3，
// 这时。我想到了先处理出假设 d[i][i] = (s[i]==b[i]) ? 0 : 1,这样处理
// 出来确实是2，然而对于例子
// zzzzzfzzzzz
// abcdefedcba
// 显然。依照我的方法是5。默认f不用刷。
//
// 细致想来，假设状态是这样定义的话，那么状态转移就会非常麻烦，由于后面
// 的状态可能并非当前状态所能转移过去的，要加上额外的开销，至于这个
// 开销是什么。我依旧没弄明确，假设有大神能指点一二。那小子双手奉上
// 2.56$,并致以最为诚挚的感激。
//
// 最后看了看网上的题解，思路差点儿都是一样的。构造dp + 线性dp
// 首先不考虑s串与b串之间的联系。
// dp[i][j]表示从空串刷成b串所须要的最小的花费。
// dp[i][j] = dp[i][k] + dp[k+1][j]{ i <= k < j}
// 假设b[i] == b[j],那么dp[i][j] = dp[i][j-1],此时b[j]全然能够由i到j-1
// 刷出来。
//
// 最后f[i]表示1到i,s串变成b串所须要的最小花费
// 假设s[i] == b[i] 那么肯定 f[i] = f[i-1];
// 否则 f[i] = min(f[j] + dp[j+1][i]);
//
// 这样最后的f[n]我们所求的答案。
//
// 这题，我感觉我终于学会的是：假设一个问题是一个非常复杂的问题，要
// 考虑非常多个方面，那么我们能够尝试分段求解，这样也许就能更加接近
// 正确的答案。继续练
//
//const int maxn = 108;
//const int inf = 0x4f4f4f4f;
//char s[maxn];
//char b[maxn];
//int d[maxn][maxn];
//bool vis[maxn][maxn];
//int n;
//int cost[maxn][maxn];
//int dp(int x,int y){
// if (vis[x][y]) return d[x][y];
// vis[x][y] = 1;
// if (x==y){
// d[x][y] = 1;
// return d[x][y];
// }
// if (x>y) return d[x][y] = inf;
// int& ans = d[x][y];
// ans = inf;
//
//
//
// for (int k=x;k<y;k++){
// ans = min(ans,dp(x,k)+dp(k+1,y));
// }
//
// if (b[x]==b[y]){
// ans = min(ans,dp(x,y-1));
// }
//
//
//
//// if (s[x]==b[x] && s[y]==b[y]){
//// ans = min(ans,dp(x+1,y-1));
//// }
//// if (b[x]==b[y]){
//// ans = min(ans,dp(x,y-1));
//// ans = min(ans,dp(x+1,y));
//// }
////
//// temp = x;
//// while(b[temp]==b[y] && temp < y){
//// temp++;
//// }
//// ans = min(ans,dp(temp,y));
//// temp = y;
////
//// while(b[x]==b[temp] && temp > x){
//// temp--;
//// }
//// ans = min(ans,dp(x,temp));
////
//// temp = x;
////
//// while(b[temp]==b[temp+1]&&temp<y){
//// temp++;
//// }
////
//// if (temp!=x)
//// ans = min(ans,dp(temp,y));
////
//// temp = y;
//// while(b[temp]==b[temp-1]&&temp>x){
//// temp--;
//// }
//// if (temp!=y)
//// ans = min(ans,dp(x,temp));
//
//
// return ans;
//}
//
//void print(){
// for (int i=0;i<n;i++){
// for (int j=0;j<n;j++){
// if (d[i][j]==inf)
// d[i][j] = 0;
// printf("%d ",d[i][j]);
// }
// puts("");
// }
//}
//
//bool same(){
// for (int i=1;i<=n;i++)
// if (s[i]!=b[i])
// return false;
// return true;
//}
//
//void init(){
// memset(d,inf,sizeof(d));
// memset(vis,0,sizeof(vis));
// memset(cast,0,sizeof(cast));
// n = strlen(s+1);
// if (same()){
// printf("0\n");
// return ;
// }
//
// int cnt = 0;
// for (int i=1;i<=n;i++){
// if (s[i]==b[i]){
// cnt++;
// }
// cost[i] = cnt;
// }
//
// printf("%d\n",dp(1,n));
// print();
//}
//
//int main() {
// freopen("E:\\Code\\1.txt","r",stdin);
// while(scanf("%s%s",s+1,b+1)!=EOF){
// init();
// // solve();
// }
// return 0;
//}
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define ceil(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define gcd __gcd
#define highBit(x) (1ULL<<(63-__builtin_clzll(x)))
#define popCount __builtin_popcountll
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const long double PI = acos(-1.L);
const int maxn = 108;
char s[maxn];
char b[maxn];
int d[maxn][maxn];
int f[maxn];
int n;
int vis[maxn][maxn];
const int inf = 0x1f1f1f1f;
int dp(int x,int y){
if (vis[x][y]) return d[x][y];
vis[x][y] = 1;
if (x==y) return d[x][y]=1;
if (x>y) return d[x][y] = inf;
int& ans = d[x][y];
ans = inf;
for (int k=x;k<y;k++){
ans = min(ans,dp(x,k) + dp(k+1,y));
}
if (b[x]==b[y]){
ans = min(ans,dp(x,y-1));
}
return ans;
}
void print(){
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
printf("%d ",d[i][j]);
}
cout << endl;
}
for (int i=0;i<=n;i++)
printf("%d ",f[i]);
cout << endl;
}
void init(){
n = strlen(s+1);
memset(d,inf,sizeof(d));
memset(vis,0,sizeof(vis));
dp(1,n);
memset(f,inf,sizeof(f));
f[0] = 0;
for (int i=1;i<=n;i++){
for (int j=1;j<=i;j++){
f[i] = min(f[i],f[j-1] + d[j][i]);
}
if (s[i]==b[i]){
f[i] = f[i-1];
}
}
//print();
printf("%d\n",f[n]);
}
int main() {
//freopen("E:\\Code\\1.txt","r",stdin);
while(scanf("%s%s",s+1,b+1)!=EOF){
init();
}
return 0;
}