提取两个字符串中最大相同部分的字符串。

香川群子

Zamyi 发表于 2015-6-19 14:16

嗯，这样倒序查，确实速度效率更高！

主要是，第1个找到的一定是最大值，然后就可以直接退出计算了……


具体检查方法的2层循环，其实是差不多的。

ili

那么热闹，我也来发个，这种算法在两个超长字符串的比较中效率较高。
代码构建了两个2000个字符的DNA序列。

1. Sub aaa()
   
2.     Dim s1 As String, s2 As String
   
3.    
   
4.     Ar = Array("A", "C", "G", "T")
   
5.     For I = 1 To 2000
   
6.         s1 = s1 & Ar(Int(Rnd * 4))
   
7.     Next
   
8.     For I = 1 To 2000
   
9.         s2 = s2 & Ar(Int(Rnd * 4))
   
10.     Next
    
11.    
    
12.     t = Timer
    
13.     a = LCS(s1, s2)
    
14.     Debug.Print Timer - t
    
15.     Debug.Print a
    
16. End Sub
    
17. Function LCS(ByVal Str1 As String, ByVal Str2 As String) As String
    
18.     Dim I As Long, J As Long
    
19.     Dim Ar, Br, Cr
    
20.     Dim Max As Long, MaxR As Long
    
21.     Dim s1  As String
    
22.     s1 = Str1
    
23.     Str1 = UCase(Str1)
    
24.     Str2 = UCase(Str2)
    
25.     ReDim Ar(1 To Len(Str1))
    
26.     For I = 1 To Len(Str1)
    
27.         Ar(I) = Mid(Str1, I, 1)     '将第一个字符串拆分为单个字符
    
28.     Next
    
29. 
    
30.     ReDim Br(1 To Len(Str2))
    
31.     For I = 1 To Len(Str2)
    
32.         Br(I) = Mid(Str2, I, 1)     '将第二个字符串拆分为单个字符
    
33.     Next
    
34.    
    
35.     ReDim Cr(1 To Len(Str1))
    
36.     For I = 1 To Len(Str2)
    
37.         For J = Len(Str1) To 1 Step -1
    
38.             If Ar(J) = Br(I) Then
    
39.                 If I = 1 Or J = 1 Then
    
40.                     Cr(J) = 1
    
41.                 Else
    
42.                      Cr(J) = Cr(J - 1) + 1
    
43.                 End If
    
44.             Else
    
45.                 Cr(J) = 0
    
46.             End If
    
47.             If Cr(J) >= Max Then
    
48.                 Max = Cr(J)
    
49.                 MaxR = J
    
50.             End If
    
51.         Next
    
52.     Next
    
53.     LCS = Mid(s1, MaxR - Max + 1, Max)
    
54. End Function

复制代码

ili

原理嘛，说难不难，说易不易。
如TCGCACGGAC 和 ATGGCTGCCA
如下图，对角线连续为1的即表示相同。

	T	C	G	C	A	C	G	G	A	C
A	0	0	0	0	1	0	0	0	1	0
T	1	0	0	0	0	0	0	0	0	0
G	0	0	1	0	0	0	1	1	0	0
G	0	0	1	0	0	0	1	1	0	0
C	0	1	0	1	0	1	0	0	0	1
T	1	0	0	0	0	0	0	0	0	0
G	0	0	1	0	0	0	1	1	0	0
C	0	1	0	1	0	1	0	0	0	1
C	0	1	0	1	0	1	0	0	0	1
A	0	0	0	0	1	0	0	0	1	0

大雨治水

经测试，都很不错 ，借来一用，谢谢分享！

我有一头小驴驴

yjh_27 发表于 2015-6-17 21:19
自定义函数

嚯，大神果然是大神，我刚好以前就被这个问题困扰好久，最后无奈放弃，今天偶尔刷到此贴，真乃神人。