1 Тема от Jumbo

  • Jumbo
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-04-28
  • Сообщений: 37

Тема: Задача на строковый алгоритм

Дан массив из N элементов и числа в нём целые от 1 до M (1<=N<=100000,1<=M<=100000). Массив - это типа кубики как они отражаются в зеркале, число M - число их цветов. Все имеющиеся кубики отражаются в зеркале а некоторые из "настоящих" кубиков тоже видны. Требуется найти количество "настоящих" кубиков (все возможные).
Например: дан массив 1 1 2 2 1 1. Может быть 3 кубика (1 1 2 - настоящие, 2 1 1 - отражение), 5 кубиков (1 - настоящий, 1 2 2 1 1 - отражение) и 6 кубиков - все отражены в зеркале.
Я решил эту задачу через хеши (вычисление хэшей всех префиксов и обратных префиксов), но видимо из-за большого M обрезание числа в int64 получается слишком большое и у меня выдаёт неправильный ответ.
Подскажите более подходящий алгоритм!

2 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: Задача на строковый алгоритм

Неужели они завалили int64-ый хеш? Что-то даже не верится smile

Если я правильно понял условие, то задача сводится к тому, что какой-то суффикс строки должен совпадать с предыдущими символами, но в обратном порядке? Т.е., выходит, должен быть палиндром на конце строки?

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

Сайтe-maxx