Goddammit. It's linear all right, but the constant factor is too
large. For two strings sized  2^20  it takes 5.9 seconds, for 2^19 it
takes 2.9 seconds, and for 2^28 it takes 1.4 seconds. That's on this
virtual machine which runs  on 2 GB of RAM.