Re: divide & conquer algorithm to implement string matching

It should be noted that this approach is extremely unfruitful!Let n be
the lenght of the main string and m the lenght of the pattern to
search on the main string.This algorithm has a time complexity of
O(O(m) * (n * O(m))),that is,if O(m) is proportional to O(n),this
gives an O(n^3) time complexity.A really really really bad algorithm.
P.S. The (n * O(m)) should be something like ((2n - 1) * O(m)), if I
consider to stop at partitions of 1 element and not 4,so I tried cut
some constant multiplicator,but it's irrelevant.


.

Relevant Pages

  • Re: divide & conquer algorithm to implement string matching
    ... the lenght of the main string and m the lenght of the pattern to ... gives an Otime complexity.A really really really bad algorithm. ... is varying,so in the divide sequence I divide less if m is bigger.So ... maybe the time complexity is inferior,I'm not sure. ...
    (comp.programming)
  • Re: divide & conquer algorithm to implement string matching
    ... Maybe I'm wrong,but to me it seems that if I consider the lenght of ... the pattern to search a constant this algorithm takes Otime to ... compute the solution,if the length of the pattern is varying,in the ... You all think I'm paranoid, ...
    (comp.programming)
  • Re: divide & conquer algorithm to implement string matching
    ... What would be more interesting is the time complexity as a function of both ... the string length and the pattern length. ... I'm guessing the D&C algorithm would be Oalso? ...
    (comp.programming)
  • RSA questions...
    ... I've been experimenting with a source code implementation of RSA. ... have a few questions about the algorithm. ... is the bit lenght the lenght of the private key? ...
    (sci.crypt)