Анаграммы

Анаграммы

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

После того как он закончил выписывать все перестановки Игорь устал и пошел учиться. Он взял словарь и начал учить новые слова. Через некоторое время Игорь заметил что некоторые из слов в словаре совпадают с записанными им перестановками на листке и задался вопросом, — а какие можно получить слова переставляя буквы из других в словаре.

Игоря будут интересовать только слова которые записаны в словаре, так как других он не знает.

Подумав несколько ночей у него получилось написать программу которая находит слово анаграмму в словаре к другому — данному. Но перед ним встал новый вопрос, — а какое слово имеет наибольшее количество анаграмм в заданном словаре.

Его программа работала слишком долго, поэтому он попросил вас написать новую которая справилась бы с этой задачей.

Входные данные

Задан словарь английских слов. Каждое слово в новой строке. Длинна слова не более $255$ символов. Количество слов любое.

Выходные данные

Вывести все слова что имеют максимальное количество анаграмм в нем.

Решение

Прочитаем словарь. Запишем в структуру pair строку с исходным словом в first и отсортированную в second. Анаграммами будут являться слова с одинаковыми second строками. Так как они будут состоять из одних и тех же букв, которые выстроены в одинаковом порядке. Отсортируем множество слов из словаря по second. Таким образом все слова анаграммы будут находиться рядом.

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

На выходе получим массив индексов слов у которых существует максимальное количество анаграмм, в данном словаре. Выведем эти слова и все анаграммы к ним в исходном варианте. Для этого нам и нужна строка  first.

Тесты

Ввод Вывод
 

1

 

2500 слов английского языка

trace react crate

dear dare read

post stop spot

Код

Код на ideone

Ю12.34

Задача.

«Балда». Для заданного достаточно длинного слова найти в имеющемся словаре все слова, в которых использованы только буквы, имеющиеся в заданном слове (с учетом кратности вхождения).

Тесты.

Ввод Вывод Комментарий
programming a in on go no an man am or arm air ring ago pain grin rain mom main among roar grip pair rip map nor aim iron program pin ma moan groan gang gain rag pig piano ramp gin ram rig Пройден
polymorphism is his him my so or room sir ship lip slip mom shop simply pop rip poor pool sip oil holy hip limp hop prop spy loom Пройден

В качестве словаря используется список 2500 наиболее употребительных английских слов (составлен Александром Васильевым).

Код(string).

Используем ввод как условие цикла while. Вводим вспомогательную строку temp, в которую записываем исходное слово. Символы строки temp, которые совпадают с символами данного слова из словаря, заменяем на точки (подходят любые символы, кроме английских букв), учитывая, таким образом, кратность вхождения. Также для проверки вводим логические переменные b1(содержатся ли все символы из строки dict в temp?) и b2(содержится ли j-ый символ из dict в temp?).

Данный код на ideone.

Код(c-string).

Решение аналогично.

Данный код на ideone.

Ю12.36

Задача: Разнобуквица. Из имеющегося словаря выбрать наиболее длинное слово, в котором  все буквы разные, например:  ЛЕЙКОПЛАСТЫРЬ, НЕРЯШЛИВОСТЬ, ЧЕТЫРЁХДЮЙМОВКА.

Тесты:

Словарь Результат Комментарий
There, here, the, then then Пройден
Список 2500 наиболее употребительных английских слов background Пройден

Код:

Для того что бы найти искомое слово создаем две строки, одна для ввода словаря, другая для результата. Создаем цикл [latex]while[/latex] . С помощью функции [latex]isalpha()[/latex] отсеиваем знаки препинания в словаре. Далее создаем булеву переменную [latex]x[/latex]  и два цикла [latex]for[/latex]  что бы проверить  встречается ли буква в слове больше одного раза, если хоть одна буква повторяется, то   присваиваем [latex]x[/latex] значение «false» и прерываем цикл [latex]for[/latex]. Если значение булевой переменной «true», значит в слове нет повторяющихся букв, из таких слов теперь можно искать самое длинное, для этого счетчику [latex]n[/latex] присваиваем размерность самого длинного слово, и присваиваем его значение  в строку [latex]max[/latex]. Выводим результат.

Ссылка Ideone.

 

Ю12.19

Задача:  В имеющемся словаре найти группы слов, записанных одними и теми же буквами и отличающиеся только их порядком, то есть перестановкой, например, (КОРМА, КОМАР).

Код:

 

Тесты:

Исходный словарь Обработанный словарь
the and a to I is of have you he it in not was that his do on with she at say her for as are we but can him they up what out me go get this from be look my there know all one no see will back into like if were then an come think so down your them would about man take just by am now over make been or time when hand who want here tell off right their turn two through eye head other how some more around door room face day where way night well thing open away give only something ask move stand good find again little try too still hear walk before leave sit let long call feel close very why which car any hold work run never start even light than after put yes stop old watch first may talk another cut mean pull behind smile our toward towards much its house keep place begin nothing year woman side because three seem wait need moment himself stare arm use voice last late across sure front sound big really name should new anything against guy kill point small happen wall black step window life maybe fall own far under boy

no
on
three
there
own
now
how
who
thing
night
its
sit
name
mean

Все слова Безымянный

Алгоритм:

Для решения данной задачи я воспользовался возможностью, которую мне предоставляет библиотека <algorithm> . Поскольку мне надо было проверить, являются ли строки перестановками строки s_tmp, которую я ставлю в роли исходной с каждой итерацией, я воспользовался функцией is_permutation .  Если некая строка является перестановкой, то она выводится на экран и стирается. С последующими итерациями будет проводится проверка на наличие на том или ином месте строки. Если строки обнаружено не будет, программа перейдёт к следующей итерации.

Для проверки правильности работы программы, воспользуйтесь ссылкой .

UPD: Поскольку я понял, что вводить вначале количество слов неудобно, я решил написать функцию, которая сама создаст массив из введённой мной строкой.