flat assembler
Message board for the users of flat assembler.

Index > Main > how to search for all strings starting with substr?

Author
Thread Post new topic Reply to topic
zhak



Joined: 12 Apr 2005
Posts: 490
Location: Belarus
zhak
Hello guys.
I'm thinking now of a solution for one problem, and still can't find the most efficient one.
lets say, i have some asciiz

a
ab
abc
ac
ba
bac
...
when i enter 'a', i need 'a','ab','abc','ac' to be displayed - all starting with a
when i enter next char (b), i need to display only 'ab','abc' and so on.
when i press backspace, i need to display all starting with 'a' again.

i'm sure there's great algorithm already discovered by wise brains to do this, but i don't know which one Smile
i would be grateful for any information... just an idea how to implement this. (small size of implementation is number one priority)
Post 06 Mar 2010, 16:04
View user's profile Send private message Reply with quote
a115433



Joined: 05 Mar 2010
Posts: 144
a115433
create a buffer to wich you put bytes or characters (a,b)
and create a variable that hold number of bytes/chars in this buffer.
create also a dynamic structure of addreses - to hold addrs of each string.
and variable that hold ammount of those addreses.
last think is buffer that holds all strings and its size
after each add or substract from character buffer, just refresh address buffer.
backspace - you would require backlink to yet another struct, but you can just use primary one (all strings) and chars/bytes in buffer.


its quite simple btw, there are no special algoritms like in crypto.
Post 06 Mar 2010, 16:15
View user's profile Send private message Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr
zhak,

If the list is sorted, binary search can be used to determine range of strings to display.

You may store strings in prefix tree, then range is just corresponding subtree.
Post 06 Mar 2010, 16:34
View user's profile Send private message Reply with quote
zhak



Joined: 12 Apr 2005
Posts: 490
Location: Belarus
zhak
i decided to keep things simple. less complicated code contains less bugs. taking into account the fact that user types with speed about 5-6 chars per second, and not very long list of supported commands (less than 30), speed is not on the first place.
i assume user input to be a substring. and i search this substring in every command. if it matches- i display the command. pretty simple, yet effective solution.
Post 08 Mar 2010, 17:51
View user's profile Send private message Reply with quote
edemko



Joined: 18 Jul 2009
Posts: 549
edemko
Post 08 Mar 2010, 19:42
View user's profile Send private message Reply with quote
zhak



Joined: 12 Apr 2005
Posts: 490
Location: Belarus
zhak
wasm.ru is online again. it was down for a while
Post 08 Mar 2010, 23:11
View user's profile Send private message Reply with quote
edemko



Joined: 18 Jul 2009
Posts: 549
edemko
Code:
; Searches for a byte pattern in another one. Count from 1.
; result <- eax.
; restore: eflags.
; Both search directions supported but result is always given as if eflags.df=0.
; -str   = wanted.
; -lstr  = length of str in bytes.
; -src   = source.
; -lsrc  = length of src in bytes.
; -start = job start relatively src's head(eflags.df=0) or tail(eflags.df=1).
; -stop  = job end(wall) relatively src's head(eflags.df=0) or tail(eflags.df=1).
proc pos uses ebx ecx edx esi edi, str:dword, lstr:dword, src:dword, lsrc:dword, start:dword, stop:dword
        pushfd
        xor     eax,eax        ; result=0

        cdq
        or      edx,[lstr]
        jz      .exit          ; length(str)=0

        mov     ecx,eax
        or      ecx,[lsrc]
        jz      .exit          ; length(src)=0

        cmp     edx,ecx
        ja      .exit          ; length(str)>length(src)

        mov     ebx,eax
        or      ebx,[start]
        jz      .exit          ; start=0
        cmp     ebx,ecx
        ja      .exit          ; start>length(src)

        mov     esi,eax
        or      esi,[stop]
        jz      @f             ; stop=0
        cmp     esi,ecx
        ja      @f             ; stop>length(src) -> stop=0
        cmp     esi,ebx
        jbe     .exit          ; start>=stop
        lea     ecx,[esi-1]    ; ecx>0 <- const

@@:     dec     ebx
        sub     ecx,ebx        ; ecx>0 <- const

        dec     edx            ; cmpsb.ecx
        sub     ecx,edx        ; scasb.ecx
        jbe     .exit          ; over(src)flow

        bt      dword[esp],10
        mov     esi,[str]
        mov     edi,[src]
        lea     eax,[edi+ebx]
        cmovnc  edi,eax
        jnc     @f             ; search TO bigger address
        neg     ebx
        add     ebx,[lsrc]
        lea     edi,[edi+ebx-1]
        add     esi,edx        ; search FROM bigger address
@@:     lodsb

@@:     repne   scasb
        jne     .fail          ; no str[1] in src
        test    edx,edx
        jz      @f             ; length(str)=1 -> no need to check the rest(edx)
        push    esi edi
        mov     ebx,ecx
        mov     ecx,edx
        repe    cmpsb
        pop     edi esi
        je      @f             ; str rest(edx) match
        mov     ecx,ebx
        jecxz   .fail
        jmp     @b

@@:     bt      dword[esp],10
        jnc     @f
        neg     edx
        lea     edi,[edi+2+edx]; switch result to be always src's head relative
@@:     sub     edi,[src]
        mov     eax,edi
        jmp     .exit

.fail:  xor     eax,eax

.exit:  popfd
        ret
endp

    
Post 08 Mar 2010, 23:26
View user's profile Send private message Reply with quote
zhak



Joined: 12 Apr 2005
Posts: 490
Location: Belarus
zhak
thanks serfasm Smile
this problem is already solved
Post 08 Mar 2010, 23:45
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.