Bidirectional Search

[horst]

Search forwards or backwards
Note that strings are passed by pointers, and the starting/returned positions by offset (0..).
It is reasonably fast (not as fast as FindString though). Assembler version (ANSI) available.

Code: Select all

; Bidirectional Find String
; Parameters: 
; *TextBase          points to string to scan
; StartOffset        where to start searching (0:beginning) 
; *string.character  points to string to find 
; CharStep           Ansi: 1 (forwards) or -1 (backwards) 

Procedure SearchString(*TextBase,StartOffset,*string.character,CharStep)
  Protected *text.character, *itext.character, *istring.character 
  
  If CharStep > 0 : CharStep = SizeOf(character)
  Else : CharStep = -SizeOf(character)    ; make sure correct value 
  EndIf 
  
  FoundOffset = -1                        ; default: not found 
  *text = *TextBase + StartOffset         ; current text pointer
  While *text\c And *text >= *TextBase    ; test for both directions 
    If *text\c = *string\c                ; 1st step: scan for 1st char
      *itext = *text                      ; if match, compare ...
      *istring = *string
      While *istring\c And *itext\c = *istring\c 
        *itext + SizeOf(character)
        *istring + SizeOf(character)
      Wend 
      If *istring\c = 0 
        FoundOffset = *text - *TextBase : Break 
      EndIf 
    EndIf 
    *text + CharStep         ; plus or minus 
  Wend 

ProcedureReturn FoundOffset  ; or -1 if not found 
EndProcedure

; Example:
; SearchString(@ObjectString,Len(ObjectString)-Len(InputString),@InputString,-1)

This routine is used in my MemPad

Edited: Example
To start search backwards the StartOffset must be set to the last byte of the ObjectString, or better: to Len(ObjectString)-Len(InputString).
Note: The StartOffset must be valid (i.e. not negative, and not beyond the last byte).

[pdwyer]

This might help you with the speed

http://www.purebasic.fr/english/viewtop ... uicksearch

I was looking at this too and got side tracked by algorithms that are faster than just checking the entire string. I didn't think there would be a faster way if the text wasn't in any way sorted... but I was very wrong.

QuickSearch is one of a series of algorithms that are faster than just looping though the string (known as a naive search apparently). It will be slower for short string or strings were the key string is only one or two chars but larger longer searches can be substantially faster.

Also I'm not sure what the "character" structure is but if you can just save the size at the beginning then you will save some CPU cycles by not having to check the sizeof() all the time

[horst]

Yes, I remember QuickSearch. This would be faster indeed. But do we need more speed?
I use my algorithm in MemPad to search through a number of pages with notes. Though notes are usually not that large, I tested one with over 3Mb. The search toook less than half a second, but it took Windows several seconds to display the page (EditorGadget)

A fast search would be good, if you have many files with lots of megabytes, but then again it would not make much sense to search backwards.. :roll:

> ... save some CPU cycles by not having to check the sizeof() all the time

You mean SizeOf(character)? That's not a runtime function. The compiler sets it to 1 or 2 (Ansi/Unicode)

[NoahPhense]

Hey that's the answer to:

What is your girlfriend doing on the internet late at night:

- np