Re: divide & conquer algorithm to implement string matching

On 29 May 2007 05:27:12 -0700, misterio <giagimari@xxxxxxxxx> 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?


If I understand the requirements properly you could do it like this:

Let n be the length of the large string and k be the length of the small
string. Start at position (n-k)/2 and examine bits in turn until you find
one that matches the start of the small string. Call that position p.
Then the right hand partition starts at p and ends at n. The left hand
partition starts at 1 and ends at p+k-1. (Adjust indexing to taste.)

In your example 01101011001100110110 would be partitioned into
0110101100110 and 1100110110.

This problem illustrates a principle that often is not articulated, namely
that divide and conquer partitions may have a soft boundary between the
partitions.



.

Relevant Pages

  • Re: Volume IDs
    ... It's a string of digits (xxxx-xxxx) assigned to the partition when - I ... think that having multiple partitions with the same volid would hurt ...
    (microsoft.public.windowsxp.general)
  • AMO question
    ... Dim oNewPartitionExists As Partition ... Dim sPartitionPrefix As String ... "Partition", sNewPartitionName, sQueryText, sProcessingType, sCalendarDWID, ...
    (microsoft.public.sqlserver.olap)
  • Re: divide & conquer algorithm to implement string matching
    ... a string like "01101011001100110110".Does anybody has any idea? ... Then the right hand partition starts at p and ends at n. ... that divide and conquer partitions may have a soft boundary between the ...
    (comp.programming)
  • Re: divide & conquer algorithm to implement string matching
    ... a string like "01101011001100110110".Does anybody has any idea? ... Then the right hand partition starts at p and ends at n. ... that divide and conquer partitions may have a soft boundary between the ...
    (comp.programming)
  • 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)