#include<iostream>
#include<string.h>
using namespace std;
int min(int a,int b)
{
return a>b?b:a;
}
int min(int a,int b,int c)
{
return min((min(a,b)),c);
}
int fun(char st1[],char st2[],int i,int j,int h1,int h2)
{
if((i>h1)&&(j>h2))
return 0;
if(i>h1)
return (h2-j+1);
if(j>h2)
return (h1-i+1);
if(st1[i]==st2[j])
return (fun(st1,st2,i+1,j+1,h1,h2));
else
return min((1+fun(st1,st2,i+1,j,h1,h2)),
(1+fun(st1,st2,i,j+1,h1,h2)),
(1+fun(st1,st2,i+1,j+1,h1,h2)));
}
int main()
{
char st1[]="geks";
char st2[]="gekpss";
cout<<fun(st1,st2,0,0,strlen(st1)-1,strlen(st2)-1);
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHN0cmluZy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgbWluKGludCBhLGludCBiKQp7CglyZXR1cm4gYT5iP2I6YTsKfQppbnQgbWluKGludCBhLGludCBiLGludCBjKQp7CglyZXR1cm4gbWluKChtaW4oYSxiKSksYyk7Cn0KaW50IGZ1bihjaGFyIHN0MVtdLGNoYXIgc3QyW10saW50IGksaW50IGosaW50IGgxLGludCBoMikKewoJaWYoKGk+aDEpJiYoaj5oMikpCgkgICAgcmV0dXJuIDA7CglpZihpPmgxKSAKCSAgIHJldHVybiAoaDItaisxKTsKCWlmKGo+aDIpCgkgICByZXR1cm4gKGgxLWkrMSk7CglpZihzdDFbaV09PXN0MltqXSkKCSAgIHJldHVybiAoZnVuKHN0MSxzdDIsaSsxLGorMSxoMSxoMikpOwoJZWxzZSAKCSAgIHJldHVybiBtaW4oKDErZnVuKHN0MSxzdDIsaSsxLGosaDEsaDIpKSwKCSAgICAgICAgICAgICAgKDErZnVuKHN0MSxzdDIsaSxqKzEsaDEsaDIpKSwKCSAgICAgICAgICAgICAgKDErZnVuKHN0MSxzdDIsaSsxLGorMSxoMSxoMikpKTsKCSAgIAp9CmludCBtYWluKCkKewoJY2hhciBzdDFbXT0iZ2VrcyI7CgljaGFyIHN0MltdPSJnZWtwc3MiOwoJY291dDw8ZnVuKHN0MSxzdDIsMCwwLHN0cmxlbihzdDEpLTEsc3RybGVuKHN0MiktMSk7CglyZXR1cm4gMDsKfQ==