Программа C++ для поиска самого длинного общего префикса с использованием сортировки

Опубликовано: 20 Сентября, 2022

Постановка задачи: по заданному набору строк найдите самый длинный общий префикс.
Примеры:

Input: {"geeksforgeeks", "geeks", "geek", "geezer"}
Output: "gee"

Input: {"apple", "ape", "april"}
Output: "ap"

 

Самый длинный общий префикс для массива строк — это общий префикс между двумя самыми непохожими строками. Например, в данном массиве {"яблоко", "обезьяна", "зебра"} нет общего префикса, потому что две самые разные строки массива "обезьяна" и "зебра" не имеют общих начальных символов.
Мы обсудили пять различных подходов в постах ниже.

  1. Пословное сопоставление
  2. Сопоставление символов по символам
  3. Разделяй и властвуй
  4. Бинарный поиск.
  5. Использование Trie)

 

В этом посте обсуждается новый метод, основанный на сортировке. Идея состоит в том, чтобы отсортировать массив строк и найти общий префикс первой и последней строки отсортированного массива.

Выход:

The longest common prefix is : gee

Временная сложность: O(MAX * n * log n ), где n — количество строк в массиве, а MAX — максимальное количество символов в любой строке. Обратите внимание, что сравнение двух строк займет не более O(MAX) времени, а для сортировки n строк нам потребуется время O(MAX * n * log n).
Пожалуйста, обратитесь к полной статье о самом длинном общем префиксе с использованием сортировки для получения более подробной информации!

РЕКОМЕНДУЕМЫЕ СТАТЬИ