Sliding String Comparison

Category: Strings

Date: 03-28-2012

Return to Index


 
'Some image processing and decryption algorithms require the comparison of
'text strings - sliding one over the other and looking for matching overlapped
'string sections.
 
'Primary Code:
'For length reasons, the primary code is shown only in the compilable example
'below.  Note that the Function (SlidingComparison) uses pointers for speed.
 
'Compilable Example:
#Compiler PBWin 9, PBWin 10
#Compile EXE
#Dim All
#Include "Win32API.inc"
Global hDlg as DWord
 
Function PBMain() As Long
   Dialog New Pixels, 0, "Test Code",300,300,200,200, %WS_OverlappedWindow To hDlg
   Control Add Button, hDlg, 100,"Push", 50,10,100,20
   Dialog Show Modal hDlg Call DlgProc
End Function
 
CallBack Function DlgProc() As Long
   If CB.Msg = %WM_Command AND CB.Ctl = 100 AND CB.Ctlmsg = %BN_Clicked Then
      Dim iStart As Long, iEnd As Long, Result As String, A as String, B as String
      A = "abcdx"  :  B = "cdxab"
      iStart = GetTickCount
      Result = SlidingComparison( 1000000, A, B)
      iEnd = GetTickCount
      MsgBox "Strings:" + $crlf + A + $crlf + B + $crlf + $crlf + Format$((iEnd - iStart)/1000,3) & " seconds" + $crlf + $crlf + "Matches:" + $crlf  + Result
   End If
End Function
 
Function SlidingComparison(iLoops&, A as String, B as StringAs String
   'strings must be equal length in this version
   Local pEndA As Byte Pointer, pStartB As Byte Pointer, sLength As Long, iNotMatchFlag As Long, Matches$, X As Long
   Local iMisMatch As Long, pATemp As Byte Pointer, pBTemp As Byte Pointer, i As Long, j As Long, pStartA As Byte Pointer
   sLength  = Len(A)
   pEndA    = StrPTR(A) + sLength - 1
   pStartA  = StrPTR(A)
   pStartB  = StrPTR(B)
 
   For x = 1 To iLoops&
      Matches$ = ""
 
      For i = 1 To sLength                           ' i is the amount of overlap
         iNotMatchFlag = 0
         For j = 1 To i
            pATemp = pEndA - i + j
            pBTemp = pStartB + j - 1
            If @pATemp <> @pBTemp Then
               iNotMatchFlag = 1
               Exit For
            End If
         Next j
         If iNotMatchFlag = 0 Then  Matches$ = Matches$ + " " + Str$(i)   'don't use this line - slow string statement
      Next i
 
      For i = 2 To sLength                            ' i is the amount of overlap
         iNotMatchFlag = 0
         For j = i To sLength
            pATemp = pStartA - i + j
            pBTemp = pStartB + j - 1
            If @pATemp <> @pBTemp Then
               iNotMatchFlag = 1
               Exit For
            End If
         Next j
         If iNotMatchFlag = 0 Then  Matches$ = Matches$ + " " + Str$(i+sLength)  'don't use this line - slow string statement
      Next i
 
   Next X
   Function = Matches$
 
End Function
 
'gbs_00410
'Date: 03-10-2012


created by gbSnippets
http://www.garybeene.com/sw/gbsnippets.htm