#elements of seq A in seq B

[John Machin]

On Aug 20, 12:12 pm, Simon Forman <sajmik... at gmail.com> wrote:
> On Aug 19, 8:17 pm, "Jan Kaliszewski" <z... at 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)