Я бы начал очень просто. Создайте 2 вектора строк, один из которых отсортирован как обычно, а другой - по двум последним буквам. Создайте индекс (вектор целых) для второго вектора, который указывает его положение в первом.
Чтобы найти самое длинное .. сначала удалите сирот. слова, которые не совпадают ни с одного конца ни с чем. Затем вы хотите построить сосед, соединяющий дерево , здесь вы можете определить, какие слова могут достигать друг друга. Если у вас 2 или более деревьев, вы должны сначала попробовать самое большое дерево.
Теперь с деревом ваша задача найти редкие концы, связать их с другими концами и повторить. Это должно дать вам довольно хорошее решение, если оно использует все слова «ваш золотой», пропустите другие деревья. Если этого не произойдет, вы сделаете целый ряд алгоритмов, чтобы сделать это эффективным.
Некоторые пункты для рассмотрения:
Если у вас 3+ уникальных конца, вы гарантированно отбросите 1+ слов.
Это может быть использовано для сокращения ваших попыток во время поиска ответа.
часто пересчитывать уникальные цели.
Нечетные числа данного конца гарантируют, что один должен быть отброшен (вы получаете 2 халявы на концах).
Отделяйте слова, которые могут соответствовать самому себе, вы всегда можете бросить их последними, и иначе они испортят математику.
Возможно, вам удастся создать маленькие самосогласованные кольца, вы можете относиться к ним как к самоподобным словам, если вы не осиротите их при создании. Это может сделать производительность фантастической, но не гарантирует идеального решения.
Пространство поиска - это порядок (N!), Список миллионов элементов может быть трудно доказать точный ответ. Конечно, я мог что-то упустить из виду.