Доброе время суток, коллеги. Я начинающий программист. Пишу на Дельфи. Столкнулся с такой алгоритмической задачей:

Что дано:
Есть текстовый файл, содержащий большое кол-во строк (до 10000). Строки состоят из слов, которых может быть до 7 в строке.
Для удобства слова будем обозначать английскими буквами.

Что нужно получить:
Список строк по следующему принципу.
1. Берем строку, состоящую из 1 слова, например, 'a', выводим ее.
2. Ищем все строки, состоящие из 2 слов и содержащие 'a'.
3. Далее для всех найденных на шаге 2 строк ищем строки, состоящие из 3 слов, содержащие оба слова исходной строки, выводим их.
4. Аналогично, ищем 4-словники, содержащие все слова любого из найденных 3-словников, выводим их. И так далее, пока строки будут находиться.
5. Когда подходящих строк уже не оказывается, мы выбираем другую строку из 1 слова, т. е. переходим к шагу 1.

Уточнения:
Любая строка обрабатывается не более одного раза.
Порядок слов в строке при поиске значения не имеет.

Что уже сделано:
1. Слова занесены в хэш-таблицу и однозначно определяются своим индексом, чтобы работать не со строками string, а с массивами чисел, где каждый элемент - число, обозначающее определенное слово.
2. Строки отсортированы с помощью кучи в порядки возрастания кол-ва слов.

Собственно, в чем вопрос: есть ли оптимальный алгоритм, выполняющий поиск следующей подходящей строки (шаг 3)?

Конечные автоматы. ИМХО оптимальнее некуда. Это самый оптимальный алгоритм по сложности(не сложности написания )

Конечно, можно поколдовать с хэш-таблицей, но это куда дольше и не гарантирую, что строка будет обрабатываться один раз. Хотя...
Для хэш таблицы есть вариант. Пусть все слова- простые числа в хэш таблице. Тогда каждую строку можно записать как произведение всех слов в ней(на глазок- числа для разных строк разные будут(разные строки- отличающиеся более чем на 1 слово)). Итак. Берем строку, которую будем искать в других. Просто делим строку, в которой ищем на строку которую ищем. Если число целое, то получили true. Но произведение слов и его уникальность надо проверить. Вообще юзай автоматы ;)

Мысль про произведение мне понравилась, благодарю. Хотя сложность там все равно квадратичная получается от кол-ва строк.
А что есть автоматы?

Это сообщение отредактировал(а) Yura_Matsuk - 10.10.2007, 18:49

Почитай любую книжку по Дискретной Математике для студентов. Там должно быть. Но сперва смотри оглавление 
В двух словах- автомат позволяет производить поиск подстроки в строке за линейное время. Вроде так. Давно ими не занимался  Я все так, в общем, знаю.

Поскольку выбор "однословных" строк произволен, достаточно исходный текст отсортировать не по количеству слов, а тупо так по алфавиту.

Или я чего-то не понимаю, или Вы ошибаетесь. Ведь при таком порядке:

Строка a b не обработается, а должна.

Слушайте, либо вам нужнолиболибо вам нужно более внятно объяснить, чего именно вы добиваетесь.