O(n^2) is bad - can it be fixed?

[Panu A Kalliokoski]

Courageous <jkraska1 at san.rr.com> wrote:

> The correct thing to do if performance becomes important
> to you in this context is to convert the string to a list,
> manipulate it as a list, and then convert it back to a string.

Interesting that nobody mentioned this: because strings are immutable, a
string produced by concatenation could be represented by a tree node of
the two substrings instead of a copy of the original character arrays.  
This works because the substrings are guaranteed to remain the same.  
String handling will become more complex so that this might not be worth
doing, but in the example case it would keep the performance O(n) for the
test.

Panu Kalliokoski