Codeforces and Polygon may be unavailable between Aug. 17, 19:00 (UTC) to Aug. 17, 22:00 (UTC) due to planned power outages. ×

Krot's blog

By Krot, 12 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