On Aug 20, 12:12 pm, Simon Forman <sajmik...@gmail.com> wrote: > On Aug 19, 8:17 pm, "Jan Kaliszewski" <z...@chopin.edu.pl> wrote: > > If you mean: to count non overlaping occurences of string A in B > > -- simply: > > > B.count(A) > > You don't want to use count() in a case like this because it iterates > through B len(A) times, i.e. this algorithm is O(A x B).
There's seems to be multiple confusion here. Jan was talking about counting non-overlapping occurrences of string A in [string] B. In that case B.count(A) is nowhere near O(A*B)... in fact in reasonable cases it is sub-linear i.e. O(B/A) See http://svn.python.org/view/python/trunk/Objects/stringlib/fastsearch.h?revision=68811&view=markup And even a naive implementation of str.count() would not "iterate through B len(A) times". and list.count() can't be used on its own to solve Neal's problem; its arg is a single element so it would have to be wrapped in a loop: sum (B.count(a) for a in A) which would of course be O(A*B) -- http://mail.python.org/mailman/listinfo/python-list
