Re: divide & conquer algorithm to implement string matching

On 30 Mag, 21:42, Willem <wil...@xxxxxxxx> wrote:
Probably. If the length of the pattern is constant, then the most
straightforward iterative solution is also O(n).
What would be more interesting is the time complexity as a function of both
the string length and the pattern length. Say, if the string length is n,
and the pattern length is m. Then the most basic algo would be O(n*m).
I'm guessing the D&C algorithm would be O(n*m) also ?
P.S.: It would actually be more like O((n-m+1)*m) but I'm not sure how
big-oh notation works with multiple variables.
If you look closely at the message that you commented I've said
exactly that!I said that in the worst case,ie when m = 1/2n,this
algorithm is O(n^2).

.

Relevant Pages

  • Re: the lowest number of comparisons in string matching
    ... pattern is located in the last place you are looking at) is m (the length ... (pattern string aka "needle" is length n, ... For a similar discussion of a more complex algorithm, ... M-1 repetitions of that character preceded by a single instance of a ...
    (comp.programming)
  • Re: divide & conquer algorithm to implement string matching
    ... 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 ... gives an Otime complexity.A really really really bad algorithm. ...
    (comp.programming)
  • Re: Predicting the Future and Kolmogorov Complexity
    ... Predictability is based on the pattern itself. ... addition to the string. ... For any prediction scheme, there are computable strings that show no ... Out of this hole comes a ~2 cm blue marble followed by a red ...
    (talk.origins)
  • This Weeks Finds in Mathematical Physics (Week 226)
    ... The first week they had lots of talks on "higher-dimensional rewriting", ... to find two files that give the same bit string. ... Now, if you're a mathematician, the whole idea of a cryptographic ... You can see the algorithm for this ...
    (sci.math.research)
  • This Weeks Finds in Mathematical Physics (Week 226)
    ... The first week they had lots of talks on "higher-dimensional rewriting", ... to find two files that give the same bit string. ... Now, if you're a mathematician, the whole idea of a cryptographic ... You can see the algorithm for this ...
    (sci.physics.research)