optimization question

[Paul Rubin]

Andrew Koenig <ark at research.att.com> writes:
> If s and t are strings, and I evaluate an expression of the form
> 
>     s[i:j] == t
> 
> can I count on the implementation not to form s[i:j] as a new
> substring?  Suppose, for instance, that s is many megabytes
> long, i and j are far apart, and t is very short.  Can I assume
> that the execution time for this comparison will be no worse
> than O(len(t)), or must I assume O(j-1)?

I don't understand.  If i and j are far apart and t is very short--
in particular, if j-i > len(t) and j < len(s), then s[i:j]==t is
always false.

Do you mean you want to search for t in that range of s?  You could
use the regexp module for that.