optimization question

[Tim Peters]

[Andrew Koenig]
> 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?

Yes, but not for the reason you're picturing <wink>:  strings are immutable
and don't support slice assignment, i.e. this code raises TypeError.

> 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)?

It's O(1) but in a useless sense.  If you do the equivalent with
array.array('c') objects, or even lists of characters, it's then true that
no sub-array i:j is formed, and it does take O(len(t)) time to copy in the
new slice.  It *also* takes O(len(s)-j) time to "shift over" the tail end of
s, unless len(t) == j-i (in which case no tail shift is needed).  All
assuming 0 <= i <= j <= len(s).