字符串的相似性

kscinow

今天偶尔看了一下Linux下的diff命令，其原理到是很简单
就是一个DP，相关题目都曾出现在ACM/ICPC的分区赛上，就是字符串编辑的那道，好象是上海赛区的吧
不过又把方程看了一边，下面是一些想法
先把题目说一下 给定字符串S，T 对S和T进行删除和插入操作，使得S和T变成一样的字符串
决定S和T的最小操作步骤
DP方程就是 D[I][J]=min(D[I-1][J-1]+S[I]==T[J]?0:1,D[I][J-1]+1,D[I-1][J]+1}
这个方程很常见，其实我们可以从图的方面来理解这个方程D[I][J]是个二维表，所以把他想成二维的格子图，那么这个方程也表示了从左上角到右下角的一种路径走法，比如格子里有宝物，你只能向下或向右走 从左上到右下然后再回到左上 能得到最多宝物是多少
还有LCSDP方程跟这个也很像，对于LCS的一个比较好的推广是求最长的连续公共子串，类似的题目如POJ的2774，当然这个题目用DP会超时的，要用到SUFFIX TREE
从DP方程入手，会发现很多题目，虽然题目变化多端，但是方程却都惊人的一致！
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/23305/showart_163153.html