Apropos your first example it really was O(n^2) all the time, I just ran a bunch of tests on various optimization settings and the strlen gets called every iteration of the loop.

I think you owe 'bwithe' a beer.