Добавим все строки в бор, тогда общий префикс двух строк это какой-то путь от корня. При этом общий суффикс это будут два пути из терминальных вершин вверх. Сделаем тогда решение за $O(L \cdot n)$. Переберем пары терминальных вершин, поднимемся вверх пока символы равны, найдем их LCA и обновим ответ. Это работает за $O(L \cdot n)$, так как по каждому ребру поднимемся не более, чем $n$ раз.

Улучшим это решение, уменьшив число проходов по одному ребру. Будем в каждом вершине поддерживать бор на обратных строках, которые закончились в поддереве. Чтобы получить суммарный бор из детей, воспользуемся техникой переливания. Возьмем наибольший по размеру бор и за $O(1)$ получим его в текущей вершине. Пройдемся по всем остальным детям и за размер меньшего бора добавим все строки из него в большой пар. Во время добавления новой вершины мы можем обновить ответ, посмотрев на две самые глубокие подстроки в поддереве. Данный алгоритм работает за $O(L \log L)$, так как каждую строка строка добавляется только в бор хотя бы в два раза больший.