[算法]最长公共子序列

mcard

首先我很差异，这么经典的算法为什么没人发（我估计也没人用）

最长公共子序列

问题

给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。
比如两个串为：
ABCD
EACB
其中AC是他最长的公共子序列

输入

1. 第一行：字符串A
   
2. 第二行：字符串B
   
3. //其中字符串A和字符串B的长度小于1000

复制代码

输出

1. 输出最长的子序列，如果有多个，随意输出1个。

复制代码

输入示例

1. 第一行：j9ZBv331f9
   
2. 第二行：F933NPf7FbjP
   
3. //来自“精易模块”-“文本_取随机字符()”

复制代码

输出示例

1. 933f

复制代码

实现思路：网上其实很多的，我在此不复制了。（太懒）





示例代码：
最长公共子序列.zip (638.37 KB, 下载次数: 25)

2017-1-22 12:50 上传

点击文件名下载附件


引用模块、支持库：精易模块、核心支持库

纯代码：

  

子程序名	返回值类型	公开	备 注
最长公共子序列	文本型
参数名	类 型	参考	可空	数组	备 注
文本一	文本型
文本二	文本型

变量名	类 型	静态	数组	备 注
Char1	文本型		0
Char2	文本型		0
Long1	整数型
Long2	整数型
Matrix	整数型		0
i	整数型
j	整数型
k	整数型
return	文本型

' 输出调试文本 (文本一)
' 输出调试文本 (文本二)
文本_逐字分割 (文本一, Char1)
文本_逐字分割 (文本二, Char2)
Long1 ＝ 取文本长度 (文本一)
Long2 ＝ 取文本长度 (文本二)
重定义数组 (Matrix, 假, Long1, Long2)
Matrix [1] [1] ＝ 1  ' matrix[0][0]=1
变量循环首 (2, Long1, 1, i)  ' for(int i = 1;i<=long1,i++){
Matrix [i] [1] ＝ 1  ' matrix[i][0]=1
变量循环尾 ()  ' }
变量循环首 (2, Long2, 1, i)  ' for(int i = 1;i<=long2,i++){
Matrix [1] [i] ＝ 1  ' matrix[0][i]=1
变量循环尾 ()  ' }
变量循环首 (2, Long1, 1, i)  ' for(int i = 1;i<=long1,i++){
变量循环首 (2, Long2, 1, j)  ' for(int j = 1;i<=long2,i++){
如果 (Char1 [i － 1] ＝ Char2 [j － 1])  ' if (char1[i-1] == char2[j-1]) {
Matrix [i] [j] ＝ Matrix [i － 1] [j － 1] ＋ 1  ' matrix[i][j] = matrix[i - 1][j - 1] + 1;
Matrix [i] [j] ＝ 选择 (Matrix [i － 1] [j] ＞ Matrix [i] [j － 1], Matrix [i － 1] [j], Matrix [i] [j － 1])  ' Math.max(matrix[i - 1][j], matrix[i][j - 1])
' }
变量循环尾 ()  ' }
变量循环尾 ()  ' }
i ＝ Long1  ' int i = m, j = n;
j ＝ Long2
k ＝ 1  ' int k = 1;
判断循环首 (k ≠ Matrix [Long1] [Long2])  ' while (k != matrix[m][n]) {
如果真 (Matrix [i － 1] [j] ＝ Matrix [i] [j])  ' if(matrix[i-1][j]==matrix[i][j]]){
i ＝ i － 1  ' i--;}
到循环尾 ()
如果真 (Matrix [i] [j － 1] ＝ Matrix [i] [j])  ' if(matrix[i][j-1]==matrix[i][j]]){
j ＝ j － 1  ' j--;}
到循环尾 ()
如果真 (Matrix [i] [j] ≠ Matrix [i － 1] [j － 1])
return ＝ Char1 [i － 1] ＋ return  ' StringBuilder.insert(0,char1[i-1]);
' 输出调试文本 (Char1 [i － 1])
k ＝ k ＋ 1  ' k++;
i ＝ i － 1  ' i--;
j ＝ j － 1  ' j--;
判断循环尾 ()
返回 (return)

.版本 2<br /> <br /> .子程序 最长公共子序列, 文本型<br /> .参数 文本一, 文本型<br /> .参数 文本二, 文本型<br /> .局部变量 Char1, 文本型, , "0"<br /> .局部变量 Char2, 文本型, , "0"<br /> .局部变量 Long1, 整数型<br /> .局部变量 Long2, 整数型<br /> .局部变量 Matrix, 整数型, , "0"<br /> .局部变量 i, 整数型<br /> .局部变量 j, 整数型<br /> .局部变量 k, 整数型<br /> .局部变量 return, 文本型<br /> <br /> ' 输出调试文本 (文本一)<br /> ' 输出调试文本 (文本二)<br /> <br /> 文本_逐字分割 (文本一, Char1)<br /> 文本_逐字分割 (文本二, Char2)<br /> <br /> Long1 ＝ 取文本长度 (文本一)<br /> Long2 ＝ 取文本长度 (文本二)<br /> <br /> 重定义数组 (Matrix, 假, Long1, Long2)<br /> <br /> Matrix [1] [1] ＝ 1  ' matrix[0][0]=1<br /> <br /> .变量循环首 (2, Long1, 1, i)  ' for(int i = 1;i<=long1,i++){<br />     Matrix <i> [1] ＝ 1  ' matrix<i>[0]=1<br /> .变量循环尾 ()  ' }<br /> <br /> .变量循环首 (2, Long2, 1, i)  ' for(int i = 1;i<=long2,i++){<br />     Matrix [1] <i> ＝ 1  ' matrix[0]<i>=1<br /> .变量循环尾 ()  ' }<br /> <br /> .变量循环首 (2, Long1, 1, i)  ' for(int i = 1;i<=long1,i++){<br /> <br />     .变量循环首 (2, Long2, 1, j)  ' for(int j = 1;i<=long2,i++){<br />         .如果 (Char1 [i － 1] ＝ Char2 [j － 1])  ' if (char1[i-1] == char2[j-1]) {<br />             Matrix <i> [j] ＝ Matrix [i － 1] [j － 1] ＋ 1  ' matrix<i>[j] = matrix[i - 1][j - 1] + 1;<br />         .否则<br />             Matrix <i> [j] ＝ 选择 (Matrix [i － 1] [j] ＞ Matrix <i> [j － 1], Matrix [i － 1] [j], Matrix <i> [j － 1])  ' Math.max(matrix[i - 1][j], matrix<i>[j - 1])<br />         .如果结束<br />         ' }<br /> <br />     .变量循环尾 ()  ' }<br /> <br /> .变量循环尾 ()  ' }<br /> <br /> i ＝ Long1  ' int i = m, j = n;<br /> j ＝ Long2<br /> <br /> k ＝ 1  ' int k = 1;<br /> <br /> .判断循环首 (k ≠ Matrix [Long1] [Long2])  ' while (k != matrix[m][n]) {<br />     .如果真 (Matrix [i － 1] [j] ＝ Matrix <i> [j])  ' if(matrix[i-1][j]==matrix<i>[j]]){<br />         i ＝ i － 1  ' i--;}<br />         到循环尾 ()<br />     .如果真结束<br />     .如果真 (Matrix <i> [j － 1] ＝ Matrix <i> [j])  ' if(matrix<i>[j-1]==matrix<i>[j]]){<br />         j ＝ j － 1  ' j--;}<br />         到循环尾 ()<br />     .如果真结束<br />     .如果真 (Matrix <i> [j] ≠ Matrix [i － 1] [j － 1])<br />         return ＝ Char1 [i － 1] ＋ return  ' StringBuilder.insert(0,char1[i-1]);<br />         ' 输出调试文本 (Char1 [i － 1])<br />         k ＝ k ＋ 1  ' k++;<br />     .如果真结束<br />     i ＝ i － 1  ' i--;<br />     j ＝ j － 1  ' j--;<br /> .判断循环尾 ()<br /> 返回 (return)

后记：
注释中为java代码，本代码按照原java代码翻译而来

明天自然醒

1. .版本 2
   
2. 
   
3. .子程序 最长公共子序列相似度2, 双精度小数型, , 稍微改进，可匹配中文但有BUG
   
4. .参数 文本一, 文本型
   
5. .参数 文本二, 文本型
   
6. .局部变量 Char1, 文本型, , "0"
   
7. .局部变量 Char2, 文本型, , "0"
   
8. .局部变量 Long1, 整数型
   
9. .局部变量 Long2, 整数型
   
10. .局部变量 Matrix, 整数型, , "0"
    
11. .局部变量 i, 整数型
    
12. .局部变量 j, 整数型
    
13. .局部变量 k, 整数型
    
14. .局部变量 return, 文本型
    
15. .局部变量 a, 正则表达式类
    
16. .局部变量 aa, 正则表达式类
    
17. 
    
18. 
    
19. a.创建 (“\S”, 文本一, , , , )
    
20. aa.创建 (“\S”, 文本二, , , , )
    
21. 
    
22. Long1 ＝ a.取匹配数量 ()
    
23. Long2 ＝ aa.取匹配数量 ()
    
24. 
    
25. 重定义数组 (Matrix, 假, Long1, Long2)
    
26. 
    
27. Matrix [1] [1] ＝ 1  ' matrix[0][0]=1
    
28. 
    
29. .变量循环首 (2, Long1, 1, i)  ' for(int i = 1;i<=long1,i++){
    
30.     Matrix [i] [1] ＝ 1  ' matrix[i][0]=1
    
31. .变量循环尾 ()  ' }
    
32. 
    
33. .变量循环首 (2, Long2, 1, i)  ' for(int i = 1;i<=long2,i++){
    
34.     Matrix [1] [i] ＝ 1  ' matrix[0][i]=1
    
35. .变量循环尾 ()  ' }
    
36. 
    
37. .变量循环首 (2, Long1, 1, i)  ' for(int i = 1;i<=long1,i++){
    
38. 
    
39.     .变量循环首 (2, Long2, 1, j)  ' for(int j = 1;i<=long2,i++){
    
40.         .如果 (a.取匹配文本 (i － 1, ) ＝ aa.取匹配文本 (j － 1, ))  ' if (char1[i-1] == char2[j-1]) {
    
41.             Matrix [i] [j] ＝ Matrix [i － 1] [j － 1] ＋ 1  ' matrix[i][j] = matrix[i - 1][j - 1] + 1;
    
42.         .否则
    
43.             Matrix [i] [j] ＝ 选择 (Matrix [i － 1] [j] ＞ Matrix [i] [j － 1], Matrix [i － 1] [j], Matrix [i] [j － 1])  ' Math.max(matrix[i - 1][j], matrix[i][j - 1])
    
44.         .如果结束
    
45.         ' }
    
46. 
    
47.     .变量循环尾 ()  ' }
    
48. 
    
49. .变量循环尾 ()  ' }
    
50. 
    
51. i ＝ Long1  ' int i = m, j = n;
    
52. j ＝ Long2
    
53. 
    
54. k ＝ 1  ' int k = 1;
    
55. 
    
56. .判断循环首 (k ≠ Matrix [Long1] [Long2])  ' while (k != matrix[m][n]) {
    
57.     .如果真 (Matrix [i － 1] [j] ＝ Matrix [i] [j])  ' if(matrix[i-1][j]==matrix[i][j]]){
    
58.         i ＝ i － 1  ' i--;}
    
59.         到循环尾 ()
    
60.     .如果真结束
    
61.     .如果真 (Matrix [i] [j － 1] ＝ Matrix [i] [j])  ' if(matrix[i][j-1]==matrix[i][j]]){
    
62.         j ＝ j － 1  ' j--;}
    
63.         到循环尾 ()
    
64.     .如果真结束
    
65.     .如果真 (Matrix [i] [j] ≠ Matrix [i － 1] [j － 1])
    
66.         return ＝ a.取匹配文本 (i － 1, ) ＋ return  ' StringBuilder.insert(0,char1[i-1]);
    
67.         ' 输出调试文本 (Char1 [i － 1])
    
68.         k ＝ k ＋ 1  ' k++;
    
69.     .如果真结束
    
70.     i ＝ i － 1  ' i--;
    
71.     j ＝ j － 1  ' j--;
    
72. .判断循环尾 ()
    
73. 
    
74. 返回 (选择 (Long1 ＞ Long2, 求字数 (return) ÷ aa.取匹配数量 (), 求字数 (return) ÷ a.取匹配数量 ()))
    
75. [code].版本 2
    
76. 
    
77. .子程序 求字数, 整数型
    
78. .参数 text, 文本型
    
79. .局部变量 a, 正则表达式类
    
80. 
    
81. a.创建 (“\S”, text, , , , )
    
82. 返回 (a.取匹配数量 ())
    

复制代码

[/code]

明天自然醒

出现中文字符也出错

明天自然醒

wwsw和wsw，www和www, 类似的文本对比出现bug

ULTRAYAN

感谢楼主热心分享！

天生是蠢材

调试输出 (计算_最长公共子序列 (“123456”, “123456”))
输出为: “12345”
我对这个算法不了解...
算法就是这样的？还是有问题？

陌杰v587

666

mcard

无名侠 发表于 2017-1-22 15:13
厉害呢

说一下实用性(来自互联网)

检查生物基因相似度(比较文本相似度？)

无名侠

厉害呢

红颜脸庞仍娇俏

本代码按照原java代码翻译而来