Какова лучшая структура данных и алгоритм для сравнения списка строк?
-
13-10-2019 - |
Вопрос
Я хочу найти самую длинную последовательность слов, которые соответствуют следующим правилам:
- Каждое слово может использоваться не более раз
- Все слова - строки
- Две строки
sa
а такжеsb
может быть объединен, если последние два персонажаsa
соответствует первым двум персонажамsb
.
В случае концентрации это выполняется путем перекрытия этих символов. Например:
- SA = "Torino"
- SB = "Новара"
- sa concat sb = "torinovara"
Например, у меня есть следующий входной файл, "input.txt":
Новара
Торино
Верцелли
Равенна
Наполи
Ливерно
Мессания
новигур
Рома
И вывод приведенного выше файла в соответствии с вышеуказанными правилами должны быть:
Торино
Новара
Равенна
Наполи
Ливорно
новигур
Поскольку самая длинная конкатенация:
torinovaravennapolivornovilligure
Кто -нибудь может помочь мне с этим? Что будет лучшей структурой данных для этого?
Решение
Это может быть представлено в виде задачи направленной графики-узлы-это слова, и они соединены краем, если они перекрываются (и наименьшее перекрытие выбирается, чтобы получить самую длинную длину), а затем найдите путь, не вмешанный на высокий вес. Анкет
(Ну, на самом деле, вы хотите немного развернуть график, чтобы справиться с началом и заканчиванием одним словом. Примыкание «стартового узла» с краем к каждому слову длины веса / 2. Между словами, -Overlap + продолжительность начала длины + Длина отделка / 2, и между каждым словом и «окончательным узлом» «длина слова / 2». Может быть легче удвоить его.)
https://cstheory.stackexchange.com/questions/3684/max-non-overlapping-path-inweeed-граф
Другие советы
Я бы начал очень просто. Сделайте 2 вектора струн, один из которых сортируется обычно, один сортируется по последним 2 буквам. Создайте индекс (вектор INT) для второго вектора, который указывает на свою позицию в первом.
Чтобы найти самые длинные .. сначала удалите сирот. Слова, которые не совпадают ни в одном конце. Тогда вы хотите построить сосед присоединится Дерево, именно здесь вы определяете, какие слова могут достичь друг друга. Если у вас есть 2 или более деревьев, вы должны сначала попробовать самое большое дерево.
Теперь с деревом ваша работа - найти конца, которые редки, и связывать их с другими концами и повторить. Это должно принести вам довольно хорошее решение, если оно использует все слова, которые ваши золотые, пропустите другие деревья. Если это не так, то вы в целый ряд алгоритмов, чтобы сделать это эффективным.
Некоторые элементы для рассмотрения: если у вас есть 3+ уникальных концов, вы гарантированно отбросите 1+ слова. Это может быть использовано для обрезки ваших попыток при охоте на ответ. Часто пересчитывайте уникальные концы. Нечетное количество данного конца убедитесь, что нужно отбросить (вы получаете 2 халявы на концах). Разделяют слова, которые могут самостоятельно совпадать, вы всегда можете бросить их в последнее время, и в противном случае они грязи. Возможно, вы сможете создать маленькие кольца с самообожением, вы можете относиться к ним как к самообосному словам, если вы не орошате их, когда вы создаете их. Это может сделать производительность фантастическим, но никаких гарантий на идеальном решении.
Пространство поиска - это заказ (n!) Список миллионов элементов может быть трудно доказать точный ответ. Конечно, я мог бы что -то упускать из виду.