Question

求最长公共子序列

数据如下：
① 03020113082000041105000002469043: bc:d1:77:96:28:12 bc:d1:77:4b:83:34 20:dc:e6:b1:c8:82 20:dc:e6:b1:c8:82 c0:61:18:7a:f6:84 5c:63:bf:e4:ee:e0 20:dc:e6:b1:c8:82 00:5a:39:3d:0d:5e 14:e6:e4:8a:9d:ee 20:dc:e6:7e:d2:44 bc:d1:77:96:28:12 bc:d1:77:4b:83:34 fc:c8:97:4e:25:5b 5c:63:bf:e4:ee:e0 08:10:78:29:f6:cb 20:dc:e6:b1:c8:82 e4:d3:32:0e:4f:30 bc:d1:77:4b:83:34 08:10:78:29:ea:f3 14:e6:e4:8a:9d:ee bc:d1:77:4b:83:34 bc:d1:77:4b:83:34 e4:d3:32:0e:4f:30
② 03020113082021204004000083967485: bc:d1:77:96:28:12 bc:d1:77:4b:83:34 20:dc:e6:b1:c8:82 20:dc:e6:b1:c8:82 c0:61:18:7a:f6:84 5c:63:bf:e4:ee:e0 20:dc:e6:b1:c8:82 00:5a:39:3d:0d:5e 14:e6:e4:8a:9d:ee 20:dc:e6:7e:d2:44 bc:d1:77:96:28:12 bc:d1:77:4b:83:34 8c:be:be:28:9e:39 8c:be:be:28:9e:39 fc:c8:97:4e:25:5b 5c:63:bf:e4:ee:e0 08:10:78:29:f6:cb 20:dc:e6:b1:c8:82 e4:d3:32:0e:4f:30 bc:d1:77:4b:83:34 08:10:78:29:ea:f3 14:e6:e4:8a:9d:ee bc:d1:77:4b:83:34 bc:d1:77:4b:83:34 e4:d3:32:0e:4f:30

上面两个数据，开头的一串数字是每一行的id（唯一），冒号后面是一些mac地址。现在想要找出这两行中mac地址的最长公共子序列（注意是子序列，也即各个mac之间不一定相连）。
谢谢！

Answer 1

　　)递归方法求最长公共子序列的长度

　　1)设有字符串a[0...n]，b[0...m]，下面就是递推公式。

　　当数组a和b对应位置字符相同时，则直接求解下一个位置；当不同时取两种情况中的较大数值。