給2 個字串，請你輸出他們的最長共同子序列（longest common subsequence）的長度。也就是說，在這兩個字串各自所有的子序列之中，內容相同而且長度最長的那個子序列。舉例來說有兩個字串abcdgh 和aedfhr，它們的最長共同子序列為adh，長度為3。
輸入說明：
輸入檔含有多筆測試資料，每筆測試資料為二行字串，每行最多有 1000 個字元。
輸出說明：
對輸入的每筆測試資料，輸出它們最長共同子序列的長度。
輸入範例：
a1b2c3d4e
zz1yy2xx3ww4vv
abcdgh
aedfhr
輸出範例：
4
3
Dim A, B
回覆刪除Private Sub Form_Load()
Me.Hide
Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
Do While Not EOF(1)
Input #1, A
Input #1, B
Call A1
Loop
Close
Close
End
End Sub
Sub A1()
c = 0
ans = 0
For i = 1 To Len(A)
ma = Mid(A, i, 1)
For j = 1 To Len(B)
mb = Mid(B, j, 1)
If ma = mb And j > c Then ans = ans + 1: c = j: Exit For
Next
Next
Print #2, ans
End Sub
Dim x As String
回覆刪除Dim y As String
Private Sub Form_Load()
Me.Hide
Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
Do While Not EOF(1)
Line Input #1, x
Line Input #1, y
List1.Clear: List2.Clear
For i = 1 To Len(x)
Call ABC(Mid(x, i, 1))
Next i
Max = 0
For i = 0 To List1.ListCount - 1
L = Len(List1.List(i))
If Max = 0 Or Max < L Then Max = L
Next i
Print #2, Max
Loop
Close #2
Close #1
End
End Sub
Sub ABC(A)
For i = 1 To Len(y)
If Mid(y, i, 1) = A Then
If List1.ListCount = 0 Then List1.AddItem A: List2.AddItem i
Call find(i, A)
End If
Next i
End Sub
Sub find(A, B)
For i = 0 To List2.ListCount - 1
If Val(List2.List(i)) < A Then List1.AddItem List1.List(i) & B: List2.AddItem A
Next i
End Sub
--------------in.txt-------------
a1b2c3d4e
zz1yy2xx3ww4vv
abcdgh
aedfhr
acbdef
abdefc
--------------out.txt-------------
4
3
5
arro好，
回覆刪除程式並不正確，這題其實還滿難的，可以去網路上找找之前的解題方法，不容易理解。
但是你的方法，已經解了一半，可以將a,b的字串互換，每組做兩次，找大值，會對哦。
A = "abcdekf"
B = "kabcdef"
柯佑好，
回覆刪除你的程式也不正確。
同樣用上面那組輸入，再將x,y互換輸入一次，應該相同答案的，但是你(們)的答案都是2和6
OK 應該是這樣子
回覆刪除當初上網在找這個"最長共同子序列"
卻找不出個感想來
Dim A, B
Private Sub Form_Load()
Me.Hide
Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
Do While Not EOF(1)
Input #1, A
Input #1, B
Call A1
Print #2, (List1.List(List1.ListCount - 1) - 20000)
Loop
Close
Close
End
End Sub
Sub A1()
pp = 1
Do
c = 0
ANS = 0
For i = pp To Len(A)
ma = Mid(A, i, 1)
For j = 1 To Len(B)
mb = Mid(B, j, 1)
If ma = mb And j > c Then ANS = ANS + 1: c = j: Exit For
Next
Next
List1.AddItem ANS + 20000
pp = pp + 1
Loop Until pp = Len(A)
End Sub
熊掌好，
回覆刪除照老師方法再將x,y互換輸入一次，
再找最大值
Dim x As String
Dim y As String
Private Sub Form_Load()
Me.Hide
Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
Do While Not EOF(1)
Line Input #1, x
Line Input #1, y
Max = 0
List1.Clear: List2.Clear
For i = 1 To Len(x)
Call ABC(Mid(x, i, 1), y)
Next i
For i = 0 To List1.ListCount - 1
L = Len(List1.List(i))
If Max = 0 Or Max < L Then Max = L
Next i
List1.Clear: List2.Clear
For i = 1 To Len(y)
Call ABC(Mid(y, i, 1), x)
Next i
For i = 0 To List1.ListCount - 1
L = Len(List1.List(i))
If Max = 0 Or Max < L Then Max = L
Next i
Print #2, Max
Loop
Close #2
Close #1
End
End Sub
Sub ABC(A, B)
For i = 1 To Len(B)
If Mid(B, i, 1) = A Then
If List1.ListCount = 0 Then List1.AddItem A: List2.AddItem i
Call find(i, A)
End If
Next i
End Sub
Sub find(A, B)
For i = 0 To List2.ListCount - 1
If Val(List2.List(i)) < A Then List1.AddItem List1.List(i) & B: List2.AddItem A
Next i
End Sub