# 思路：dp[i][j] 表示两个字符串分别取到 i, j 位的时候的距离，考虑 a[i] 和 b[j]，有两种情况
# 1、a[i] == b[j]，则 dp[i][j] = dp[i-1][j-1]
# 2、a[i] != b[j]，则 dp[i][j] = min([dp[i-1][j-1], dp[i][j-1], dp[i-1][j]]) + 1


while True:
    try:
        a, b = input(), input()
        dp = []
        for i in range(len(a)+1):
            dp.append([0] * (len(b)+1))
        for i in range(len(a)+1):
            dp[i][0] = i
        for j in range(len(b)+1):
            dp[0][j] = j
        
        for i in range(1, len(a)+1):
            for j in range(1, len(b)+1):
                if a[i-1] == b[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min([dp[i-1][j-1], dp[i][j-1], dp[i-1][j]]) + 1
                    
        print(dp[len(a)][len(b)])
    except:
        break

#请教各位大佬我想法的错误之处。 #1.对两个字符串进行排序
#2.选择两字符串最小字符的最大值为起点，最大字符的最小值为终点，遍历其中所有字符
#3.如果其中存在二者相等的字符，那么继续向后查找，直到其不再相等，标记其位置
#4.在相等字符前的长度（取二者的最大值）为需要删除/增加之字符
#5.递归查询3中位置之后的字符串


while True:
    try:
        
        def align(s1,s2):
            global cou
            start=max(s1[0],s2[0])#开始字符
            end=min(s1[-1],s2[-1])#结束字符
            
            for i in range(ord(start),ord(end)+1):#i is number
                chri=chr(i)
                if chri in s1 and chri in s2:
                    pos1=s1.index(chri)
                    pos2=s2.index(chri)
                    cou+=max(pos1,pos2)
                    break
            elses1=len(s1)-1
            elses2=len(s2)-1
            while s1[pos1]==s2[pos2] and pos1!=elses1 and pos2!= elses2:
                pos1+=1
                pos2+=1
                
            if pos1==elses1&nbs***bsp;pos2==elses2:
                cou+=max(elses1-pos1,elses2-pos2)
                return 0
            else:
                align(s1[pos1+1:],s2[pos2+1:])

        s1=sorted(input())
        s2=sorted(input())
        cou=0
        align(s1,s2)
        print(cou)
        
    except:
        break

def edit_distance(s1,s2):
    len1 = len(s1) + 1
    len2 = len(s2) + 1
    edit = [[i + j for j in range(len2)] for i in range(len1)]
    for i in range(1,len1):
        for j in range(1,len2):
            if s1[i-1] == s2[j-1]:
                d = 0
            else:
                d = 1
            edit[i][j] = min(edit[i][j-1]+1,edit[i-1][j]+1,edit[i-1][j-1]+d)
    return edit[-1][-1]

while True:
    try:
        print(edit_distance(input(), input()))
    except:break

# -*- coding: utf-8 -*-
# !/usr/bin/python3
# 解题思路：动态规划dp[i][j]表示st1[0:j - 1]和st2[0:i - 1]的最小距离；
# 那么st1和st2的距离与dp[i][j], dp[i - 1][j]和dp[i][j - 1]有关；
# 如果st1[j] == st2[i], dp[i + 1][j + 1] = dp[i - 1][j - 1];
# 如果st1[j] != st2[i], dp[i + 1][j + 1] = min(dp[i - 1][j - 1], dp[i - 1][j] + 1, dp[i][j - 1] + 1);
# 边界条件：第0行和第0列表示空字符串分别于st1和st2的子字符串的距离，dp[i][0] = i, dp[0][j] = j


while True:
    try:
        st1 = input()
        st2 = input()

        if len(st1) < len(st2):
            st1, st2 = st2, st1

        m = len(st1)
        n = len(st2)

        res = [[0 for i in range(m + 1)] for i in range(n + 1)]

        for i in range(n + 1):
            res[i][0] = i

        for j in range(m + 1):
            res[0][j] = j

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if st1[j - 1] == st2[i - 1]:
                    res[i][j] = res[i - 1][j - 1]
                else:
                    res[i][j] = min(res[i - 1][j - 1] + 1, res[i - 1][j] + 1, res[i][j - 1] + 1)

        print(res[n][m])

    except:
        break

'''
生成大小为(N+1)*(M+1)的矩阵dp. dp[x][y]表示A前x个字符串编辑成 B前y个字符所花费的代价.
对于第一行来说,dp[0][y]表示将一个空串变为B的前y个字符组成的子串,花费的代价为ic*y;
同理,对于第一列dp[x][0] = x*dc;

对于其他的位置,dp[x][y]可能有以下几种取值:
    dp[x-1][y-1]+rc;//A[x-1]!=B[y-1] 将前x-1个字符变为B前y-1个字符,再将最后一个字符替换.
    dp[x-1][y-1];//A[x-1]==B[y-1] 将前x-1个字符变为B前y-1个字符,最后一个不用修改.
    dp[x-1][y]+dc;//删除一个字符,将前x-1个字符变为B的前y个字符
    dp[x][y-1]+ic;//将A前x-1个字符变为B的前y个字符,再插入一个字符
    dp[x][y]的值就为以上四者最小的一个.
求解完毕,dp[n][m]即为所求.
--------------------- 
作者：shizheng163 
来源：CSDN 
原文：https://blog.csdn.net/shizheng163/article/details/50988023 
版权声明：本文为博主原创文章，转载请附上博文链接！

'''
while True:
    try:
        #动态规划问题 n*m的矩阵
        datax=input()#竖着放
        datay=input()#横着放
        n=len(datax)+1#要修改的字符串长度
        m=len(datay)+1#修改后的字符串长度
        ic=1#插入操作
        dc=1#删除操作
        rc=1#修改操作
        dp=[]
        for i in range(n):
            dp.append([0]*m)
        for y in range(m):
            dp[0][y]=ic*y
        for x in range(n):
            dp[x][0]=rc*x
        for x in range(1,n):
            for y in range(1,m):
                if datax[x-1]==datay[y-1]:
                    case1=dp[x-1][y-1]
                else:
                    case1=dp[x-1][y-1]+rc
                case2=dp[x-1][y]+dc
                case3=dp[x][y-1]+ic
                dp[x][y]=min(case1,case2,case3)

        print(dp[n-1][m-1])
    except:
        break
    

# 经典的动态规划题目，matrix[i][j]代表string1的前i个字符转换到string2前j个字符的
编辑距离,根据第i个字符和第j个字符是否相等就可以得到matrix[i][j]的表达式
def LevenDistance(string1,string2):
    m = len(string2)
    n = len(string1)
    matrix = [[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(1,n+1):
        matrix[i][0] = i 
        for j in range(1, m + 1):
            matrix[0][j] = j
            if string1[i-1] == string2[j-1]:
                matrix[i][j] = min([matrix[i-1][j-1],matrix[i-1][j]+1, matrix[i][j-1]+1])
            else:
                matrix[i][j] = min([matrix[i-1][j-1] , matrix[i-1][j], matrix[i][j-1]]) + 1
    return matrix[n][m]

while True:
    try:
        string1 = input().strip()
        string2 = input().strip()
        print(LevenDistance(string1,string2))
    except:
        break

python solution:

def editDistance(str1, str2):
    len1, len2 = len(str1) + 1, len(str2) + 1
    dp = [[0 for i in range(len2)] for j in range(len1)]
    for i in range(len1):
        dp[i][0] = i
    for j in range(len2):
        dp[0][j] = j
    for i in range(1, len1):
        for j in range(1, len2):
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (str1[i - 1] != str2[j - 1]))
    return dp[-1][-1]


while True:
    try:
        print(editDistance(input(), input()))
    except:
        break

def string_distance(a,b):
    m = len(a) + 1
    n = len(b) + 1
    dp = [[0] * n for i in range(m)] # dp[m][n]
    for i in range(m):
        dp[i][0] = i
    for i in range(n):
        dp[0][i] = i

    for i in range(1,m):
        for j in range(1,n):
            cost = 0 if a[i-1]== b[j-1] else 1
            d1 = dp[i-1][j-1] + cost
            # d2 = dp[i-1][j-1] + 1
            d3 = dp[i-1][j] + 1
            d4 = dp[i][j-1] + 1
            dp[i][j] = min(d1, d3, d4)
    return dp[m-1][n-1]

while True:
    try:
        a = raw_input()
        b = raw_input()
        print string_distance(a,b)
    except:
        break