Tag: POJ

Part 1： 题目描述 许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为： 1.修改一个字符（如把“a”替换为“b”）; 2.增加一个字符（如把“abdd”变为“aebdd”）; 3.删除一个字符（如把“travelling”变为“traveling”）; 比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案，都仅需要一 次 。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离+1”的倒数。也就是说，“abcdefg”和“abcdef”的距离为1，相似度 为1/2=0.5。 给定任意两个字符串，你是否能写出一个算法来计算它们的相似度呢？ Part 2：分析 书中给出的解法是通过递归来做的。其实有更快更简便的方法——动态规划。 此题其实就是算法中的求“最短编辑距离”。 编辑距离定义：计算两个字符串的距离，完全相同的字符串距离为0，可以通过修改一个字符、增加一个字符或删除一个字符三种方式来使两个字符串相同，但这些方式会使得距离加1。 假设现在有两个字符串A和B A：David B：Taisy 用二维数组d[i][j]表示A中取前i个字符到B中取前j个字符的最短编辑距离。比如d[2][1]就代表从”Da”到”T”的最短编辑距离。这里为2（即把D换成T，去掉A 或者去掉D，把a换成T）。 首先我们作出初始化d[0][j] = j（字符串A子串长度为0，字符串B子串有多少个字符，就作多少次增加操作；于是同理，作删除操作，可得d[i][0] = i） 其中d[i][j]只有3个来源： 1). 来自d[i – i][j – 1]，即 “A的前i-1个字符组成的子串” 到 “B的前j-1个字符组成的子串” 的编辑距离，此时如果A[i] = B[j]，则最短编辑距离不变，否则最短编辑距离加1（即把A[i]变为B[j] ），所以d[i][j] = d[i – 1][j – 1] + (A[i] == B[j] ?  0 : 1) […]