Построим бор по всем 2 × n строкам. Теперь решаем следующую задачу: разделить строки, заканчивающиеся в вершинах, на такие пары, что в каждой паре вершина одной строки является предком вершины другой (в таком случае первая будет префиксом второй).
Обходим наш бор с помощью обхода в глубину, начиная из вершины, соответствующей пустой строке. Попадая в вершину, добавляем номера всех строк, которые в ней заканчиваются, в стек. Затем запускаем обход в глубину по очереди от каждого ребенка вершины.
После этого будем смотреть на последний элемент стека. Если он равен номеру какой-то строки, заканчивающейся в текущей вершине, значит мы не сопоставили эту строку кому-то из строк в вершинах-потомках текущей вершины. Значит, единственное, что остается — сопоставить эту строку либо с такой же неиспользованной строкой из текущей вершины, если такая имеется, либо с какой-то еще не использованной строкой из вершины-предка, то есть второму сверху элементу стека (все неиспользованные вершины лежат в стеке в порядке входа в них, значит вершина второй строки сверху будет нестрогим предком текущей). Удаляем два верхних элемента и повторяем процедуру со следующим элементом на вершине стека.
Асимптотика: O(L), где L - суммарная длина всех строк.