Re: Big O and algorithm to decide string A contains string B?

(There's nothing in this specific to C++ or Java, so I've deleted those
two newsgroups.)
> From: "Siemel Naran" <SiemelNaran@xxxxxxxxxxxxxx>
> Decrement expect[c] by one, but if it is zero then don't decrement it.
> Now check if all the elements in expect are zero.

No. Keep one extra counter that is the number of characters not yet
matched, which is initially the length of string B. Whenever you
actually decrease expect[c] (because it was positive, not zero,
beforehand), you also decrease that extra counter. When the extra
counter reaches zero, you know all characters in B have been found in A
all the required number of times. (This can happen only when you've
just decreased some expect[c] to zero, and this fact can be used as a
check against accounting bugs.) If you run off the end of A without
already terminating, then you know to return false.

Of course if B is large but constant, you can optimize by building the
expect[*] array just once, and making a copy of it each time the
function is called with same B but different A. On the other hand, if A
is large and constant, you want to compile have[*] for A once and
compare it against expect[*] for each different B.
.

Relevant Pages