Задача с собеседования на стажировку в Яндекс

Оригинальная задача, которая достаточно большое количество подходов к решению, тем не менее интервьювер ожидал чуть менее эффективное решение, по сравнению с самыми быстрми, но самое простое. Давайте разберем все способы.

Итак задача:
Дано n строк, сумма длин которых не превосходит 10^5, для каждой строки st[i] требуется найти позицию строки j, у которой длина наибольшего общего префикса максимальна возможной.

1 способ:
Наиболее лаконичный и даже подходящий под ограничения.
Отсортируем все строки (сохранив индексы изначальных позиций для каждой строки), получив просто лексикографический порядок, тогда для каждой строки одна из двух соседних будет соотвествовать нужной.
Итоговая асимптотика O(S log n), где S - сумма длин всех строк.

2 способ:
Воспользуемся структурой данных бор. Построим его и в каждой вершине будем сохранять два любых индекса строки (которые имеют такой же префикс, как путь от корня до данной вершины). Далее пройдемся по списку строк и для каждой строки будем спускаться по бору, тогда на каждой иттерации спуска в вершине будет храниться два индекса (один возможно совпадет с индексом текущей и на такой случай, второй будет как раз нужным). Если в какой-то момент на спуске будет вершина лишь с одним индексом, совпадающим с текущим, то остановимся.
Итоговая асимптотика O(S), где S - сумма длин всех строк

3 способ:
Пройдемся по каждой строке в наборе и параллельно будем поддерживать хеш каждого префикса и добавлять его в unordered_map (хеш мапу), и каждому хешу в мапе сопоставим два индекса (как в предыдщем решении). Затем пройдемся по каждой строке второй раз и поддержим хеш каждого префикса, соответственно найдем в мапе хеш префикса максимальной длины и получим ответ для каждой строки.
Итоговая асимптотика O(S), где S - сумма длин всех строк.

@algoses