people with a large vision only

[Lior]

Hey.
I wondered, lets say I have 2 strings:
1) "ABBACCCCABCCABAAAACBBA"
2) "CABACAAABACCABBAAACBBA"

and I wanna know the max common string between them,
how do I do it?
I dont want the function to have a run time of more than O(n*n).

In other words, I need a very efficient algorythm.
I dont want the simple solve of a double-loop. its too easy and too moron. I need something brilliant & efficient.

[G.Kumaraguru]

Hi ,
ARE you working in the GENOME Project.. ?

Is it a GENETIC Sequence your WORKING ON ???

REGARDING Algorithms...

TRY THIS ...

STONY BROOK ALGORITHM REPOSITORY
http://www.cs.sunysb.edu/~algorith/

BEST OF LUCK.

[G.Kumaraguru]

WOW..this is great... I found it for you..

JUMP TO

http://www.cs.sunysb.edu/~algorith/f...ubstring.shtml

[Iain17]

This is the best i can come up with of the top of my head.

Option Explicit

Private Sub Command1_Click()
    MsgBox findMaxString(Text1.Text, Text2.Text)
End Sub

Private Function findMaxString(str1 As String, str2 As String) As String
    Dim ip1 As Integer, ip2 As Integer
    Dim strTemp As String
    
    ip1 = 1: ip2 = 1
    Do
      strTemp = Mid$(str1, ip1, ip2 - ip1 + 1)
      
      If InStr(1, str2, strTemp) > 0 Then
        ip2 = ip2 + 1
        If Len(strTemp) > Len(findMaxString) Then
          findMaxString = strTemp
        End If
      Else
        ip1 = ip1 + 1
        ip2 = ip1
      End If
    
    Loop Until ip2 > Len(str1)
      
End Function

[Mongo]

I toyed with the collection route, but found it less efficient than this. Not sure whether this still qualifies as moronic, since obviously it's double looped.

I'll continue to think on it.

Function MaxCommon(i_str1 As String, i_str2 As String) As String
Dim str As String, str1 As String, str2 As String
Dim i As Integer, j As Integer, k As Integer
  ' the no-brainer
  If i_str1 = i_str2 Then
    MaxCommon = i_str1
    Exit Function
  End If
  i = Len(i_str1)
  j = Len(i_str2)
  If i = 0 Or j = 0 Then Exit Function
  ' when can, work match from shorter 
  If i <= j Then
    str1 = i_str1:  str2 = i_str2
  Else
    str1 = i_str2:  str2 = i_str1
  End If
  ' catch easiest
  If InStr(str2, str1) > 0 Then
    MaxCommon = str2
    Exit Function
  End If
  ' get first longest
  For i = 1 To Len(str1) - 1
    j = Len(str1) - i
    str = Left$(str1, j)
    If InStr(str2, str) > 0 Then
      MaxCommon = str
      Exit Function
    End If
    str = Right$(str1, j)
    If InStr(str2, str) > 0 Then
      MaxCommon = str
      Exit Function
    End If
    If i > 1 Then
      For k = 2 To Len(str1) - j
        str = Mid$(str1, k, j)
        If InStr(str2, str) > 0 Then
          MaxCommon = str
          Exit Function
        End If
      Next k
    End If
  Next i
End Function

[Edited by Mongo on 07-14-2000 at 04:22 PM]

[Lior]

Thanks.
you really helped me.