算法题

Question

Write a Windows form application that returns the difference of two given files using Levenshtein distance (edit distance).
A commonly-used bottom-up dynamic programming algorithm for computing the Levenshtein distance involves the use of an (n + 1) × (m + 1) matrix, where n and m are the lengths of the two strings. Here is pseudocode for a function LevenshteinDistance that takes two strings, s of length m, and t of length n, and computes the Levenshtein distance between them:
翻译如下:
写一个Windows窗体应用程序，返回两个指定使用LevenshteinDistance函数（编辑距离）文件的差异。
一个常用的自下而上的动态规划算法计算Levenshtein距离涉及使用一个（n +1）×（m+ 1）矩阵，其中n和m是两个字符串的长度。下面是一个两个字符串函数LevenshteinDistance的伪代码，s是m的长度，t是n的长度，并计算它们之间的Levenshtein距离：int LevenshteinDistance(char s[1..m], char t[1..n])
   // d is a table with m+1 rows and n+1 columns
   declare int d[0..m, 0..n]
 
   for i from 0 to m
       d[i, 0] := i
   for j from 1 to n
       d[0, j] := j
 
   for i from 1 to m
       for j from 1 to n
           if s[i] = t[j] then cost := 0
                          else cost := 1
           d[i, j] := minimum(
                                d[i-1, j] + 1,     // deletion
                                d[i, j-1] + 1,     // insertion
                                d[i-1, j-1] + cost   // substitution
                            )
 
   return d[m, n]
Two examples of the resulting matrix (the minimum steps to be taken are highlighted)
两种结果矩阵（最少的步骤被采纳是突出的）The invariant maintained throughout the algorithm is that we can transform the initial segment s[1..i] into t[1..j] using a minimum of d[i,j] operations. At the end, the bottom-right element of the array contains the answer.
翻译：
整个算法的的变量保持是我们可以改变最初的片断[s1 .. i]到t[1 .j]，使用最少的d [i,j]操作。最后，数组的右下角元素包含了答案。