3 ms·

Could you store the string in multibyte form, and then keep a skip list (or other data structure) to get indexing in O(log n)?