文字幅が可変長 (utf-8) であっても windows みたいなことをするのはそんなにコスト大きくないよね？
ふたつのポインタを一文字ずつ進めるだけなんだから O(N) で出来るはず。