Доброе время суток, коллеги. Я начинающий программист. Пишу на Дельфи. Столкнулся с такой алгоритмической задачей:
Что дано:
Есть текстовый файл, содержащий большое кол-во строк (до 10000). Строки состоят из слов, которых может быть до 7 в строке.
Для удобства слова будем обозначать английскими буквами.
Что нужно получить:
Список строк по следующему принципу.
1. Берем строку, состоящую из 1 слова, например, 'a', выводим ее.
2. Ищем все строки, состоящие из 2 слов и содержащие 'a'.
3. Далее для всех найденных на шаге 2 строк ищем строки, состоящие из 3 слов, содержащие оба слова исходной строки, выводим их.
4. Аналогично, ищем 4-словники, содержащие все слова любого из найденных 3-словников, выводим их. И так далее, пока строки будут находиться.
5. Когда подходящих строк уже не оказывается, мы выбираем другую строку из 1 слова, т. е. переходим к шагу 1.
Уточнения:
Любая строка обрабатывается не более одного раза.
Порядок слов в строке при поиске значения не имеет.
Что уже сделано:
1. Слова занесены в хэш-таблицу и однозначно определяются своим индексом, чтобы работать не со строками string, а с массивами чисел, где каждый элемент - число, обозначающее определенное слово.
2. Строки отсортированы с помощью кучи в порядки возрастания кол-ва слов.
Собственно, в чем вопрос: есть ли оптимальный алгоритм, выполняющий поиск следующей подходящей строки (шаг 3)? |
)