2010年10月28日 星期四

最長共同字串

內容 ：
序列1:
序列 2:


給你2個字串，請你輸出他們的最長共同子字串（longest common subsequence）的長度。例如：給你以下2個字串：

abcdgh
aedfhr

他們的最長共同子字串為adh，長度為3。

輸入說明 ：
輸入含有多組測試資料。每一組測試資料2列，分別代表這2個字串（最多1000個字元）。
輸出說明 ：
每組測試資料輸出他們的最長共同子字串（longest common subsequence）的長度。
範例輸入 ：

a1b2c3d4e
zz1yy2xx3ww4vv
abcdgh
aedfhr
abcdefghijklmnopqrstuvwxyz
a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0
abcdefghijklmnzyxwvutsrqpo
opqrstuvwxyzabcdefghijklmn
範例輸出 ：

4
3
26
14
張貼者： 於
標籤：

5 則留言:

  1. 寫寫程式2010年10月28日 下午2:51

    Dim St1 As String, St2 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)
    Sum = 0
    Line Input #1, St1
    Line Input #1, St2
    For i = 1 To Len(St1)
    A = Mid(St1, i, 1)
    If InStr(i, St2, A) <> 0 Then
    Sum = Sum + 1
    End If
    Next i
    Print #2, Sum
    Loop
    Close #2
    Close #1
    End
    End Sub

    BY小白

    回覆刪除
  2. 寫寫程式2010年10月28日 下午3:43

    Public Sub Form_Load()
    Open App.Path & "/in.txt" For Input As #1
    Open App.Path & "/out.txt" For Output As #2
    Me.Hide
    Do Until EOF(1)
    Input #1, st1
    Input #1, st2
    m = 0: n = 0
    For i = 1 To Len(st1)
    k = Mid(st1, i, 1)
    If InStr(st2, k) <> 0 Then
    If InStr(st2, k) > n Then
    n = InStr(st2, k)
    m = m + 1
    End If
    End If
    Next i
    Print #2, m
    Loop
    Close #2
    Close #1
    End
    End Sub

    BY Yung

    回覆刪除
  3. 毛毛蟲~~2010年11月9日 下午4:45

    這題沒這麼簡單吧@@"
    兩個人的演算法都是錯的痾0.0"

    回覆刪除
  4. 寫寫程式2010年11月15日 上午8:59

    Public Sub Form_Load()
    Open App.Path & "/in.txt" For Input As #1
    Open App.Path & "/out.txt" For Output As #2
    Me.Hide
    Do Until EOF(1)
    Line Input #1, St1
    Line Input #1, St2
    k = 1
    Do Until k = Len(St1) + 1
    m = 0: n = 0
    For i = k To Len(St1)
    kk = Mid(St1, i, 1)
    If InStr(n + 1, St2, kk) <> 0 Then
    n = InStr(St2, kk)
    m = m + 1
    End If
    Next i
    k = k + 1
    If m > ans Then ans = m
    Loop
    Print #2, ans
    Loop
    End
    Close #2
    Close #1
    End Sub

    Yung

    回覆刪除
  5. 寫寫程式2010年11月15日 上午9:07

    Dim St1 As String, St2 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)
    Sum = 0
    Max = 0
    Line Input #1, St1
    Line Input #1, St2
    K = 1
    Do Until K = Len(St1) + 1
    Sum = 0
    N = 0
    For i = K To Len(St1)
    A = Mid(St1, i, 1)
    If InStr(N + 1, St2, A) <> 0 Then
    N = InStr(St2, A)
    Sum = Sum + 1
    End If
    Next i
    If Max < Sum Then Max = Sum
    K = K + 1
    Loop
    Print #2, Max
    Loop
    Close #2
    Close #1
    End
    End Sub


    BY小白

    回覆刪除

訂閱： 張貼留言 (Atom)