OK, here is the binary search method, not fully tested though, so beware. I have not implemented the reducing lookup range idea in the substring search, because for some obscure reason it was slower, probably to do with how the binary search works, though it might just have been a coding error on my part.
BTW The version of binary search I have chosen (no I did not think it up myself) is good because it just does one compare per subdivision and does not do an explicit equality test. This is I think advantageous for string searches. You can throw an equality test in there and sometimes get an early exit, but overall that extra compare just slows it down.
[edit] I have added the lookup range reduction idea back into the wordsearch function as it definately seems to improve matters with larger dictionaries and I can see no good reason why it should not be faster most of the time.
[edit] Having added range reduction a better exit strategy for the substring search presented itself, which results in another slight speedup.
Graphics 600,600,0,2
Dim Dict$(80000)
Dim Didx(30)
Dim Words(255)
; Function loads a dictionary, which is assumed to be an ascii sorted word list.
; words are stored in Dict$() and Initial character indexing in Didx()
Function LoadDict(filepath$)
File=ReadFile(filepath$)
If file=0 Then Return False
Repeat
index=index+1
word$=Lower(ReadLine(file))
dict(index)=word
Thischar=Asc(word)-96
If Thischar<>Lastchar Then Didx(Thischar)=index
Lastchar=Thischar
Until Eof(file)
Didx(Thischar+1)=index : Didx(0)=index
CloseFile file
Return index
End Function
; Function checks for word in dictionary by binary search
; if word does not exist return next nearest word.
Function Dictfind(word$,startpos,endpos)
Local top=endpos, bot=startpos-1, middle
While (top-bot)>1
middle=(top+bot)/2
If dict(middle)<word Then bot=middle Else top=middle
Wend
Return top
End Function
; Function finds words in search string with specified minimum length
Function Wordsearch(search$,minlen)
Local i,j,substr$,wcount,idx,low,high,maxlen,searchlen=Len(search)
search=Lower(search)
For i=1 To searchlen-minlen+1
maxlen = searchlen-i+1
substr = Mid(search,i,maxlen)
idx = Asc(substr)-96 : low=didx(idx) : high=Didx(idx+1)
high = dictfind(substr,low,high)
If dict(high)=substr Then wcount=wcount+1 : words(wcount)=high ;: high=high-1
For j=minlen To maxlen-1
substr=Mid(search,i,j)
low=Dictfind(substr,low,high)
; If Left(dict(low),j)<>substr Then Exit ; See improved exit strategy below.
If dict(low)=substr Then wcount=wcount+1 : words(wcount)=low : low=low+1
If low = high Then Exit ; Range reduction allows this instead of the test above
Next
Next
Return wcount
End Function
; load the OSPD (official scrabble player dictionary)
; see <a href="http://www.puzzlers.org/wordlists/dictinfo.php" target="_blank">http://www.puzzlers.org/wordlists/dictinfo.php</a>
time=MilliSecs()
wordcount=Loaddict("C:\program files\blitz3d\tmp\OSPD.txt")
If wordcount=0 Then RuntimeError " Failed to load dictionary"
time=MilliSecs()-time
Print "Dictionary Loaded in "+time+" Millisecs with ("+ wordcount+") Words"
Print
search$="AAFABASBEARNA"
wordlength=2
iterations=100
Repeat
Print "Searching for words with at least "+wordlength+" letters
Print "in String "+search
time=MilliSecs()
For i = 1 To iterations
wordcount=wordsearch(search,wordlength)
Next
time=MilliSecs()-time
Print "Searched string "+iterations+" times in "+time+" milliseconds"
Print "Found "+wordcount+" words"
For i=1 To wordcount
Print dict(words(i))
Next
wordlength=wordlength+1
Until WaitKey()=27 Or wordcount=0
End