需求场景

让我们先来看一段有趣的对话，体验下开发和运维日常

开发：你用我发你的包 再测试下

运维：改了哪里吗

开发：就改了下模板

运维：emmm，这个是模板问题吗

开发：嗯 报那个错是模版报出来的

运维：有具体的位置吗：运维

开发：你对比下那个模版

运维：没有具体位置吗

运维：这个模板有1000行，要逐行比对吗

开发：嗯，你下载个原来的，这两个文件 比对 应该就可以看出来

运维：好

通过上面的对话看出，如果我们想知道源文件修改了啥，手工匹配是非常复杂的

Linux提供了比对命令可以完美的解决运维的问题，见下图

如何实现diff命令的设计思路

a = ['a', 'b', 'c','d']

b = ['a','a3','b','c','c3','d']

那就使用费曼算法 （Feynman algorithm）。这个算法是以著名物理学家理查德·费曼命名的

1 绘制网格

在动态规划中，你要将某个指标最大化。你要找出两个文件的区别。

如何将这个问题划分为子问题呢？你可能需要比较子串：不是比较a和b两个数组，而是先比较a[0]和b[0]。每个单元格都将包含这两个子串的最长公共子串的长度。这也给你提供了线索，让你觉得坐标轴很可能是这个定位索引。因此，网格可能类似于下面这样。

2填充网格

填充该网格的每个单元格时，该使用什么样的公式呢？由于你已经知道答案——a3和f3，因此可以作点弊。

即便如此，你还是不能确定该使用什么样的公式。计算机科学家有时会开玩笑说，那就使用费曼算法 （Feynman algorithm）。这个算法是以著名物理学家理查德·费曼命名的

伪代码如下。

if word_a[i] == word_b[j]：　　　←————————两个字母相同 　

cell[i][j] = cell[i-1][j-1] + 1

else：　　 ←——————————————————————————————两个字母不同 　

cell[i][j] = max（cell[i-1][j], cell[i][j-1]）

3填充后的结果

我们看到第一列其实已经把b插入的索引位置暴露出来了，那么思路有了，如何实现呢

实现方法

Python实现

#!/usr/bin/python3
print('11111')
a = ['a', 'b', 'c','d']
b = ['a','a3','b','c','c3','d']
cell=[0]*6;
print(len(a))
d=0;
for i in range(len(b)):
   print(i)
   for j in range(len(a)):
    # j=d if d==0 else cell[i-1]-1;
    # print("jjjj====",j)
     if j>i: print("break",cell[j]);  break;
     else: j=d;
     print(cell)
     print("jjjj====",j)
     if b[i]==a[j]:
       if(cell[i-1]+1>d):
        d=1  if i==0 else cell[i-1]+1;
       cell[i]=d;
     else:
       if(cell[i-1]+1>d):
         cell[i]= 0  if i==0 else cell[i-1];
     if(d==4): d=d-1;

for i in cell:
  print("====",i)
for i in range(len(cell)):
  if(i==0): continue;
  if(cell[i]==cell[i-1]):
    print("b compare to a change index",i);

    print("a have insert code",b[i])

还有哪些实际应用

●生物学家根据最长公共序列来确定DNA链的相似性，进而判断两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。

●你使用过诸如git diff等命令吗？它们指出两个文件的差异，也是使用动态规划实现的。

●前面讨论了字符串的相似程度。编辑距离（levenshtein distance）指出了两个字符串的相似程度，也是使用动态规划计算得到的。编辑距离算法的用途很多，从拼写检查到判断用户上传的资料是否是盗版，都在其中。

●你使用过诸如Microsoft Word等具有断字功能的应用程序吗？它们如何确定在什么地方断字以确保行长一致呢？使用动态规划！