Krot's blog

By Krot, 8 years ago, In Russian,
Никак немогу понять всю пользу использования хэширования в задачах на строки. Складывается впечатление, что это нужно только для быстрого сравнения строк. Тем не менее, слышал, что многие задачи как-то очень просто решаются с использованием хэширования. Например:

http://acm.timus.ru/problem.aspx?space=1&num=1517 (умею решать за линейное время суффиксным деревом, слышал, что решается просто за O(nlogn) хэшами)

Если кому-то не трудно, напишите пожалуйста разбор данных задач, а так же может еще какие-то полезные идеи-задачи на эту тему. 

UPD. Спасибо, всем, теперь появился немного другой вопрос: можно ли использовать hash_map на соревнованиях (точнее есть ли какие-то соревнования, где таковых библиотек нету)? А то вроде как они не стандартизованы?

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it