Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 09.09.2009, 10:51
Иришка

 
Сообщений: n/a

поиск анаграм
Помогите пожалуйста. Срочно нужен алгоритм.
Задача: дан словарь, необходимо составить максимально быстрый алгоритм для поиска всех возможных анаграм.
Пример анаграмы: тропа, апорт.
  #2  
Старый 09.09.2009, 12:27
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

отсортировать буквы в словах по алфавиту.
тропа - аопрт
каждому из исходных слов сопоставить номер в массиве нового слова, каждому новому - список номеров исходных.
  #3  
Старый 09.09.2009, 13:16
Иришка

 
Сообщений: n/a

Сообщение от MBo Посмотреть сообщение
каждому из исходных слов сопоставить номер в массиве нового слова, каждому новому - список номеров исходных.
А можно подробнее. Как осущестляется после сортировки поиск?
  #4  
Старый 09.09.2009, 13:20
гость

 
Сообщений: n/a

Сообщение от MBo Посмотреть сообщение
отсортировать буквы в словах по алфавиту.
Начала упорядочивать, что-то тоже проблемы с этим, как это делается?
  #5  
Старый 09.09.2009, 15:13
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

строка есть массив символов. Сортировать - любым алгоритмом сортировки.

массив А:
0:апорт - 0
1:осел - 1
2:село - 1
3:тропа - 0

массив B:
0: аопрт - 0, 3
1: елос - 1, 2

слово "тропа" нашли бинарным поиском в первом массиве, нулевой элемент второго массива содержит индексы в первом - 0 и 3, все анаграммы.

Вместо второго массива можно хэш-таблицу использовать
  #6  
Старый 21.09.2010, 10:35
гость

 
Сообщений: n/a

MBo Тупорылеший бред...твой алгоритм...
  #7  
Старый 21.09.2010, 15:21
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Спасибо за качественный и полезный комментарий
  #8  
Старый 22.09.2010, 14:00
гость

 
Сообщений: n/a

в массиве В достаточно ранить ключ и номер слова в массиве А. Потом цикл пока в отсоритованном В и если B[i]==B[i-1], то выпечатываем A[B[i].ссылка на А]
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра