Re: divide & conquer algorithm to implement string matching

misterio wrote:
) 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 O(n) time to
) compute the solution,if the length of the pattern is varying,in the
) worst case (that should be if the lenght of the pattern is an half of
) the lenght of the main string)this algorithm could take O(n^2) time to
) compute the solution.Am I right?

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.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
.

Relevant Pages

  • Re: Serialize a Strategy Pattern List of objects with out xsi:type
    ... whether this is a strategy pattern or not. ... depends on how you define algorithm. ... As for your "secondly" comment about homework, ... suggest that you create a seperate class that you will serialize. ...
    (microsoft.public.dotnet.framework)
  • Re: Reading and writing a big file in Ada (GNAT) on Windows XP
    ... memory for a substring; this is very descriptively called memmemand ... common cases (no mapping, single character patterns, and so on). ... So in this case a better algorithm is probably the way to go (and I ... the source length is>M and the pattern length is>N, ...
    (comp.lang.ada)
  • Re: Mersenne Twister
    ... And no PRNG is unpredictable. ... >> Just give me the algorithm and the key and I can predict it ... >hard to write a test which is able to find a pattern. ... Since the key is far far shorter than the stream ...
    (sci.crypt)
  • Re: A clear difference between algorithm and a pattern
    ... A pattern is a "formalized" algorithm. ... arrangements of class abstractions. ... Dijkstra and Parnas software architecture is ...
    (comp.object)
  • Re: Search for byte pattern in a binary file.
    ... one of the algorithms posted does partially solve the buffer ... The Knuth-Morris-Pratt algorithm is a forward-only algorithm, ... If the search pattern is extremely large (on the order of several ... since disk access is extremely slow. ...
    (comp.lang.java.programmer)