Re: divide & conquer algorithm to implement string matching

misterio said:

I'm trying to find a divide & conquer algorithm to implement a string
matching program that can find occurrences of a string like "0110" in
a string like "01101011001100110110".Does anybody has any idea?

The problem you have with divide-and-conquer in this case is that it can
cause you to miss some matches. For instance, if you take your specific
example, a naive d&c algorithm would do this:

01101 01100 11001 10110
^^^^ ^^^^ ^^^^
match match miss match

which is great, because it gives you three matches, but...

01101011001100110110
^^^^^^^^

....misses these two.

In any case, d&c doesn't really buy you anything here. You could just do
this:

0110 1011 0011 0011 0110

unsigned long haystack = 0x6B336;
unsigned char needle = 0x6;
unsigned char mask = 0xF;
int i = 0;
int c = 0;

while(haystack >= needle)
{
if((haystack & mask) == needle)
{
printf("Match %d at position %d\n", ++c, i);
}
++i;
haystack >>= 1;
}

That is, you can simply shift your way through the bits, masking as you
go.

Maybe I'm missing something, but I really don't see how d&c works for
you in this situation.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
.

Relevant Pages

  • Re: ctypes & strings
    ... ctypes, it has to be a ctypes type. ... original output string ... unsigned char read_write (unsigned char *inputs, unsigned char *outputs, int ...
    (comp.lang.python)
  • Re: ctypes & strings
    ... This routine outputs and inputs a symmetric block of bytes, ... original output string ... unsigned char read_write (unsigned char *inputs, unsigned char *outputs, int ...
    (comp.lang.python)
  • Re: PHP global namespace clogged up
    ... -string strchr(string haystack, string needle) ... int strpos(string haystack, string needel ): ...
    (comp.lang.php)
  • RE: [PHP] odd behavior of stripos() with === operator *LAST POST*
    ... In a situation where you are only dealing with boolean values, ... int stripos (string haystack, string needle ) ... you the position of the needle in your haystack, ...
    (php.general)
  • Quandry with the following C code (Intermediate)
    ... The following code will compare and old string to a new one, ... int compare(unsigned char *old, unsigned char *new, int max) ...
    (comp.lang.c)