Re: divide & conquer algorithm to implement string matching

misterio wrote:
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?

Any match that exists must have a starting position at which the match
occurs. Graphically, the set of possible starting positions in your example
would be this:

01101011001100110110
ABCDEFGHIJKLMNOPQ

Positions A-Q are all the possible starting positions. You can
break this into subproblems on the basis of starting positions.
That is, by taking subsets of the set of possible starting positions.
For example, A-I and J-Q are two subsets. You could work on each
subset independently and then merge together the results.

As others have mentioned, this is not likely to gain you much
computational efficiency, though.

- Logan
.

Relevant Pages

  • Re: Index of the n-th occurrence
    ... string? ... occurrences of your_pattern ... This returns an array of the pairs of the letter and its index. ... extract the letters with map. ...
    (comp.lang.ruby)
  • Re: Replace all occurrences of a string
    ... Jim Gibson wrote: ... >>Is there a utility or command that will allow me to replace all occurrences ... >>of a string within all files in a directory? ...
    (comp.lang.perl)
  • Locate string in queries
    ... occurrences of a string (e.g. ... Change all references to field to ... the contents of all queries to locate all occurrences of a string? ... I must manually go through all the queries to find/replace the ...
    (microsoft.public.access.modulesdaovba)
  • Re: Help on cleaning strings
    ... I need to clean all the ocorrences of the "##Z/" string (without the ... If there are some occurrences of that string that need to stay or you ...
    (perl.beginners)
  • replace all occurrences of a substring in a string (RE)
    ... Anyway I would like to replace all occurrences of a substring in a string which consists of html code. ...
    (alt.php)