Сравните две строки в O (logn) с некоторой предварительной обработкой и предположением

Question

Я думаю, можно ли сравнить две строки в O (log n) с некоторой предварительной обработкой и предположением.

Моя предварительная обработка заключается в сохранении строки в виде дерева AVL, где значениеузел - это значение символа Ascii. Поскольку я использую один и тот же алгоритм для построения дерева AVL, две идентичные строки будут иметь одинаковое дерево AVL. В результате нам может не потребоваться проверка всех узлов. Можно ли проверить только O (log n) узлов, чтобы узнать, совпадают ли два дерева? Если нет, то удастся ли построить другую древовидную структуру, которая бы достигла моей цели?

Answer 1

Если вы строите дерево AVL, где значением узла является значение ASCII символа, то не приведет ли "STOP" и "SPOT" к одному и тому же дереву AVL? Что если бы строки были "aaaaaaaa" и "aaaaaaab"? Эти строки имеют длину 8 символов. Какие три персонажа вы сравните? Будет ли это работать на "аааабааа"?

Ответ - нет. Ваша идея не сработает.