40 lines
1.1 KiB
Plaintext
40 lines
1.1 KiB
Plaintext
Function LCS(a As String, b As String) As String
|
|
Dim As String x, y
|
|
If Len(a) = 0 Or Len(b) = 0 Then
|
|
Return ""
|
|
Elseif Right(a, 1) = Right(b, 1) Then
|
|
LCS = LCS(Left(a, Len(a) - 1), Left(b, Len(b) - 1)) + Right(a, 1)
|
|
Else
|
|
x = LCS(a, Left(b, Len(b) - 1))
|
|
y = LCS(Left(a, Len(a) - 1), b)
|
|
If Len(x) > Len(y) Then Return x Else Return y
|
|
End If
|
|
End Function
|
|
|
|
Function SCS(u As String, v As String) As String
|
|
Dim lcsStr As String = LCS(u, v)
|
|
Dim As Integer i, ui = 0, vi = 0
|
|
Dim As String sb = ""
|
|
For i = 1 To Len(lcsStr)
|
|
While ui < Len(u) Andalso Mid(u, ui + 1, 1) <> Mid(lcsStr, i, 1)
|
|
sb += Mid(u, ui + 1, 1)
|
|
ui += 1
|
|
Wend
|
|
While vi < Len(v) Andalso Mid(v, vi + 1, 1) <> Mid(lcsStr, i, 1)
|
|
sb += Mid(v, vi + 1, 1)
|
|
vi += 1
|
|
Wend
|
|
sb += Mid(lcsStr, i, 1)
|
|
ui += 1
|
|
vi += 1
|
|
Next
|
|
If ui < Len(u) Then sb += Right(u, Len(u) - ui)
|
|
If vi < Len(v) Then sb += Right(v, Len(v) - vi)
|
|
Return sb
|
|
End Function
|
|
|
|
Print SCS("abcbdab", "bdcaba")
|
|
Print SCS("WEASELS", "WARDANCE")
|
|
|
|
Sleep
|