Re: divide & conquer algorithm to implement string matching

misterio <giagimari@xxxxxxxxx> writes:

The real problem to correctly implement this algorithm is to find a
way to calculate the exact indices when applying the divide & conquer
approach,and tat is why in the previous implementation some of these
indices were missing.With the following code I solved this problem by
calculating a fake array dimension augmented by 2 units,and that gives
me the total coverage of the indices.Now the problem is that I need to
verify is this approach is too particular and in case how to extend it
to any lenght of the base string and the pattern to search.Now I'll
start to search a solution to this,but I think it should be possible
to find such a math formula if I maintain the divide sequence costant
(ie.dividing always by 2),or maybe it could be even possible that this
approach can work flowessly for any kind of lenghts,I still don't
know,I need to try.Anyway,in the meantime,this is the code :
(P. S. I simplified the printf code to print just the 1st index of
every sequence,so that you can see if there's one missing)


It's called "divide and conquer", not "divide by 2 and conquer".

--
__Pascal Bourguignon__ http://www.informatimago.com/

NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
.

Relevant Pages

  • Re: Access types as parameters
    ... it needs new data structures (Subproblem and List_Of_Subproblems) which may require dynamic memory allocation if the Subproblem type is complex. ... you now need a class-wide operation that invokes Divide and then Conquer for the given object of type T'Class. ... I much prefer to use the language-defined overriding of primitive operations, so I would make Mul primitive on Item, instead of class-wide, and override it with an accelerated version for those Item'Class types that allow it. ...
    (comp.lang.ada)
  • Tim Dixon is Sabras Brother, Used to post under the name of Bruce Chang
    ... Subject: Divide & Conquer ... What reasons could there be to divide and conquer the doctor/public ... The whole world, except Tim and Sabra, is in on the Conspiracy. ...
    (sci.med.dentistry)
  • RE: My thoughts on the list as of late...
    ... > Being of a cynical nature - I tend to look at things with a ... > users that are set out to divide and conquer. ... > distracted from the real goals - so that when potential users want to ...
    (freebsd-questions)
  • Re: Generic Host Process For Win32 - Ugh
    ... "ksreek" wrote: ... Perform a divide and conquer to trace the defected item ... Remove the appropriate entry that caused the problem during the divide ... I know this is something common since my wife's computer had ...
    (microsoft.public.windowsxp.general)
  • Re: Tim Dixon is Sabras Brother, Used to post under the name of Bruce Chang
    ... > Subject: Divide & Conquer ... when things were bleak for Tim and Sabra, and after Sabra had been so ... If you have unanswered health issues, ...
    (sci.med.dentistry)