Пересечение списка слов, которое извлекает строки, содержащие комбинацию двух слов

Итак, исходные данные — это отсортированный список словарных слов и список случайных несортированных строк.

Задача состоит в том, чтобы извлечь из списка со случайными строками только те, которые являются комбинацией двух слов из списка словаря.

Список словарей:

ace
dice
nice
task
test
try

Случайный список:

test123task
testtask
bbtesttask
bbtest1task
nicetry
nicetesttry
nice1task
1nicetry

Результат:

testtask
nicetry

Вы сталкивались со сценарием, который делает это и может обрабатывать большие списки? Я не совсем уверен, что смогу запрограммировать это сам. Я думаю об алгоритме, который обрабатывает список один раз и извлекает список слов, начинающихся с ключевого слова. Он должен добавить какой-то порядковый номер для буквы, на которой заканчивается первая строка.

Затем список обрабатывается еще раз, начиная с index+1 и до конца.

Приветствуются любые указания о готовом решении или с чего начать. У меня ограниченный опыт работы с PHP и MySQL.


list word intersection
person EliasP    schedule 25.11.2013    source источник
comment
Ну, это потому, что я не уделил должного внимания деталям... Я добавил это в словарь. Спасибо.   -  person EliasP    schedule 25.11.2013

Ответы (1)


arrow_upward
1
arrow_downward

Вот начало:

Возьмите слово из случайного списка:

test123task

Поиск (бинарным поиском) t в списке словарей. Если слово начинается с t, ищите te, если оно найдено, ищите tes и т. д. test1 не найдено, поэтому вы остаетесь на test, которое является фактическим словом в словаре, и ищете слово 1, ничего не начинается с 1, поэтому возвращайтесь назад. Но tes, te и t - это не слова. test123task неверно.

Другой пример:

testtask

Найдите t, te, tes, test, testt. Вернитесь на test. test — правильное слово, продолжайте отсюда. Найдите t, ta, tas, task. task - правильное слово. Вернуть успех.

Вводимые вами данные не очень интересны, потому что в некоторых случаях вам может понадобиться остановиться на более коротком слове. Добавим tes в словарь. И проверьте это слово:

`testask`

Найдите t, te, tes, test, testa. Вернитесь на test. test — правильное слово, продолжайте отсюда. Найдите a, as. Возвращайтесь в a. a - неправильное слово. Вернитесь к tes. tes — правильное слово, продолжайте отсюда. Найдите t, ta, tas, task. task есть в словаре, вернуть успех.

Из этих трех примеров вы сможете написать рекурсивный алгоритм, использующий поиск с возвратом, чтобы проверить все возможности.

person Maxime Chéramy    schedule 25.11.2013