Форум программистов, компьютерный форум CyberForum.ru

Задается словарь. Найти в нем все анаграммы - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Класс и vector http://www.cyberforum.ru/cpp-beginners/thread839028.html
всем доброго времени суток,задача состоит в том что бы данные классов хранились в векторе,что я и пытался сделать. #include <iostream> #include <algorithm> #include <vector> using namespace std; #define n 40
C++ Создать список из слов файла Подскажите пожалуйста как написать программу, которая считывает текст по словам из файла и создаёт из него список. http://www.cyberforum.ru/cpp-beginners/thread839006.html
Процедура обхода для дерева C++
постройте процедуру обхода для определения длины бинарного(или произвольного) дерева (т.е. длину максимальной ветви) PS если можно то в консольном проекте, нужен только код, спасибку поставлю))
C++ Задача на изображения
Доброе время суток программисты. Я в программировании новичок. Мне предстоит решить такую задачу: Страшный вирус режет фотографию на 4 частей и перемешивает ее. На вход на стандартном потоке ввода подаются 4 имен файлов, содержащих куски одного исходного изображения в формате jpg в случайном порядке.Нужно вывести эти же имена файлов в том порядке, в котором они составляют исходное...
C++ Буквы в словах http://www.cyberforum.ru/cpp-beginners/thread838981.html
Всем привет, у меня есть задача посмотрите если у кого есть исходник киньте спасибо. Дана непустая последовательность слов из строчных русских букв; между соседними словами – запятая, за последним словом – точка. Напечатать в алфавитном порядке все глухие согласные буквы, которые не входят хотя бы в одно слово. Примечание: глухие согласные – к, п, с, т, ф, х, ц, ч, ш, щ. ...
C++ Ошибка в коде. не найден оператор, принимающий правый операнд типа 'int' Доброго времени суток. Не понимат что за ошибка: error C2679: бинарный '>': не найден оператор, принимающий правый операнд типа 'int' (или приемлемое преобразование отсутствует). Да и вообще, правильно ли составлена программа, если задание - нахождение количества положительных и отрицательных елементов матриц. #include <iostream> #include <conio.h> #include <iomanip> using namespace std;... подробнее

Показать сообщение отдельно
gazlan
3130 / 1905 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
16.04.2013, 04:20     Задается словарь. Найти в нем все анаграммы
Поскольку для анаграммы порядок букв неважен, остаются только такие характеристики слова, как использованные буквы и их количество.

Самый простой и быстрый вариант - это испортить словарь: отсортировать внутри каждого слова все буквы по алфавиту, а затем сами слова по по алфавиту. Остальное тривиально.

Если словарь портить нельзя...

Слова с разным количеством букв анаграммами быть не могут - проверяете только слова одинакового размера. Для каждого слова создаете массив счетчиков букв (33, если не различать регистр). Если для двух слов состояния счетчиков букв совпали - они являются анаграммой.

Проходите в цикле по списку слов (словарю) и за квадратичное время находите все анаграммы.

Если словарь предварительно отсортировать по размеру и по алфавиту, то будет быстрее :-)

Как (эквивалентный) вариант, можно выбрать систему счисления с (основание) > (число букв) и (основание) > (максимальная длина слова) и присвоить каждой букве вес - значение единицы отдельного разряда. Тогда, очевидно, все анаграммы будут иметь одинаковый вес.

На первом шаге алгоритма за линейное время взвешиваем все слова, на втором - за логарифмическое - сортируем, на третьем - распечатываем все последовательности одинакового веса. На большом словаре, разница в производительности должна быть значительной.

В любом случае, задача сводится к построению метрики (оценке расстояния между словами), нечувствительной к порядку букв, но чувствительной к самим буквам и их количеству. Слова с нулевым расстоянием являются анаграммами.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru