the string can be longer than this

How long? The string length makes a huge difference in runtime.

But it is horribly slow

Define slow. Slow to some people might be really quick to others.

Typically I need to compare millions of such pairs

How many millions? 1, 10, 100, 1,000? It all makes a difference.

I think you need to show your code and some realistic data. I have basic substr-based code that will process your example data 100k+ times a second.

That, to me, is fast