Re: divide & conquer algorithm to implement string matching

On 29 May 2007 09:03:30 -0700, misterio <giagimari@xxxxxxxxx> wrote:

On 29 Mag, 16:14, c...@xxxxxxxx (Richard Harter) wrote:
On 29 May 2007 05:27:12 -0700, misterio <giagim...@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.
This is really interesting,but isn't it too varying?I mean,isn't it
possible to loose all the time complexity capabilities of divide &
conquer in some particular cases?

Indeed. My example was correct but my prose was not. (I can't imagine was
I was thinking.) Simply set p=(n-k)/2. The first partition is (1:p+k) and
the second is (p:n). The recurrence equation is

T(n) = T((n+k)/2) + T((n-k)/2)

The solution is an exercise for the student.



.

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
    ... matching program that can find occurrences of a string like "0110" in ... a string like "01101011001100110110".Does anybody has any idea? ... Then the right hand partition starts at p and ends at n. ...
    (comp.programming)
  • Re: Assemblers are for hiding your work , not for faster code .
    ... a little thing to divide a 64-bit integer by ... ATIME: CONVERT TIME TO ASCII ... STRING IN OUR "BCD" STRING BUFFER. ... The box I'm working on makes up to 20-second time delays with 1 ps ...
    (comp.arch.embedded)