доказать, ято язык принадлежит классу TIME(n log(n))

[PreVory]

Есть язык $L^{a-b}=\{a^kb^k\}$ Требуется доказать, что он принадлежит классу TIME(n log(n)), т.е. существует машина Тьюринга, разрешивающая этот язык за время, не превышающее const*n *log(n), где n-длина входного слова. Причём доказывать тот факт, что не существует лучшего времени выполнения не нужно. Ну по сути надо описать МТ, которая будет разрешивать этот язык, за время n*log(n).
Мне известно, что можно построить такую МТ, которая будет разрешивать данный язык за $o(n^2)$ следующим образом: после первого прохода по слову проверяем его структура, т.е. сначало идёт некоторое количество букв a, потом некоторое количество букв b. Если слова имеет такой вид, то стираем первую букву a, идём по слову до последней буквы b, которую тоже стираем, и так пока не кончится один из видов букв, после чего сделаем вывод о принадлежности слова языку. Ну достаточно понятно, что сложность данного алгоритма будет $o(n^2)$.
Первое что приходит в голову - модифицировать этот алгоритм следующим способом: стирать не по 1 букве, а по несколько, но тогда порядок сложности не изменится.
Поскольку в ответе в сложности есть логарифм. то мне показалось, что это можно сделать путём двоичного поиска нужных букв, но вроде его в МТ нельзя реализовать за логарифмическое время, в связи с ограниченностью алфавитов и количества состояний автомата.
Как можно модифицировать данный алгоритм, либо какой другой алгоритм сможет удовлетворять условиям?
P.S. естественно, имеется ввиду, что мы должны построить одноголовочную недетерминированную МТ.

[whitefox]

Возможно Вы имели ввиду одноленточную ДМТ?

Попробуйте подсчитать количество букв $a$ для чего потребуется $k$ раз выполнит инкремент, каждый потребует не более чем $c\cdot \log k$ операций.

[Xaositect]

Алгоритм простой - на каждом из примерно $\log n$ шагов каждую вторую букву стираем попутно замечая, четное кол-во букв или нечетное, а когда дошли до конца, сравниваем эти четности у $a$ и $b$ (это будут двоичные цифры в количестве букв).

[whitefox]

Алгоритм предложенный Xaositect лучше моего, и реализовать его проще.

[PreVory]

Действительно, получилось сделать как написал Xaositect. Спасибо)