Анаграммы
Игорю стало интересно какое количество перестановок букв его фамилии существует. Для этого он выписал на листке бумаге все буквы своей фамилии по алфавиту и начал создавать новые перестановки этих букву в лексикографическом порядке, записывая их на листок.
После того как он закончил выписывать все перестановки Игорь устал и пошел учиться. Он взял словарь и начал учить новые слова. Через некоторое время Игорь заметил что некоторые из слов в словаре совпадают с записанными им перестановками на листке и задался вопросом, — а какие можно получить слова переставляя буквы из других в словаре.
Игоря будут интересовать только слова которые записаны в словаре, так как других он не знает.
Подумав несколько ночей у него получилось написать программу которая находит слово анаграмму в словаре к другому — данному. Но перед ним встал новый вопрос, — а какое слово имеет наибольшее количество анаграмм в заданном словаре.
Его программа работала слишком долго, поэтому он попросил вас написать новую которая справилась бы с этой задачей.
Входные данные
Задан словарь английских слов. Каждое слово в новой строке. Длинна слова не более $255$ символов. Количество слов любое.
Выходные данные
Вывести все слова что имеют максимальное количество анаграмм в нем.
Решение
Прочитаем словарь. Запишем в структуру
pair строку с исходным словом в
first и отсортированную в
second. Анаграммами будут являться слова с одинаковыми
second строками. Так как они будут состоять из одних и тех же букв, которые выстроены в одинаковом порядке. Отсортируем множество слов из словаря по
second. Таким образом все слова анаграммы будут находиться рядом.
Теперь пройдемся по словарю и будем проверять соседние элементы. Если они равны, то мы будем увеличивать счетчик анаграмм, если же нет, то мы сравним максимальное количество анаграмм, найденное ранее, с текущим значением счетчика. Если они равны, то добавим индекс последнего слова анаграммы в массив индексов, если же больше, то мы очистим массив индексов и добавим туда индекс последнего слова анаграммы. В любом случае, при не равенстве соседних строк сбрасываем счетчик и продолжаем.
На выходе получим массив индексов слов у которых существует максимальное количество анаграмм, в данном словаре. Выведем эти слова и все анаграммы к ним в исходном варианте. Для этого нам и нужна строка
first.
Тесты
Код
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <iostream> #include <string> #include <algorithm> #include <vector> #define DIFFERENCE ('A' - 'a') // разность регистров using namespace std; bool IsBigAlpha(char a) { return (a >= 'A' && a <= 'Z'); } bool IsSmalAlpha(char a) { return (a >= 'a' && a <= 'z'); } string edit(const string &str) { // приводим всё к нижнему регистру и убираем лишние символы string rez = ""; for(char a : str) { if (IsBigAlpha(a)) a -= DIFERENSE; if (IsSmalAlpha(a)) rez += a; } return rez; } bool comp(const pair<string, string> &a, const pair<string, string> &b) { // сравнитель по второй строке return a.second < b.second; } int main() { vector <pair<string, string>> words; // словарь string str; while (getline(cin, str, '\n')) { pair<string, string> word; // слово word.first = str; word.second = edit(str); sort(word.second.begin(), word.second.end()); // сортируем буквы в слове words.push_back(word); } sort(words.begin(), words.end(), comp); // сортируем словарь по анаграммам vector <int> indeces; // массив индексов int Count = 0, MaxCount = 0, n = words.size(); for (int i = 1; i < n; i++) { if (words[i-1].second == words[i].second) Count++; else { if (Count > MaxCount) { MaxCount = Count; indeces.clear(); indeces.push_back(i-1); } else if (Count == MaxCount) indeces.push_back(i-1); Count = 0; } } if (Count > MaxCount) { // обрабатываем последний найденный набор анаграмм MaxCount = Count; indeces.clear(); indeces.push_back(n-1); } else if (Count == MaxCount) indeces.push_back(n-1); bool first = 1; for (int index : indeces) { // выводим if (!first) cout << endl << "---------------" << endl; else first = 0; for (int i = 0; i <= MaxCount; i++) { if (i != 0) cout << endl; cout << words[index - i].first; } } return 0; } |
Код на ideone
