William D Clinger scripsit:

> A textual->text procedure would not be O(1).  I'm guessing you
> mean the result returned by that procedure would always be a
> text, which would guarantee O(1) running time when that result
> is passed to certain other procedures.

Just so.

> The usual algorithm for naive string search, combined with the
> O(1) guarantee for text-ref, already gives you O(mn) running time.

Yes, I see.  So ignore comment 2.

> The purpose of the O(mn) requirement is to outlaw extraordinarily
> naive algorithms, such as those that extract so many subtexts they
> take Omega(m^2 n) time.

Okay, fair enough.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
A: "Spiro conjectures Ex-Lax."
Q: "What does Pat Nixon frost her cakes with?"
  --"Jeopardy" for generative semanticists