catpad (catpad) wrote,
catpad
catpad

Алгоритмическая задача

Задача пришла из жизни. Это не просто упражнение, а совершенно реальная задача, которую мне необходимо решить на работе. Я её решил, но, может быть, кто-то придумает лучше.


Дано множество строк, например:

voda
eric
nec

и так далее - размер множества любой.
На входе алгоритм получает произвольную строку, например: "vodafone.com".
Как наиболее быстрым способом определить, что эта строка содержит в качестве подстроки (substring) одну из данного множества ?
(В приведённом примере ответ положительный, потому что "voda" - это подстрока "vodafone.com").

Задача простая, но ключевые слова здесь, конечно - "наиболее быстро".
Я придумал как это сделать почти за линейное время. "Почти" в смысле, что я не очень хорошо помню, что такое "amortized complexity", но, кажется, получается как раз O(n).
Завтра опубликую ответ, но хотелось бы посмотреть на разные предложения.

Subscribe

  • (no subject)

    Зачем-то прослушал «Трудно быть богом». Последний раз читал её в школе. Лишний раз убедился, как же всё-таки быстро эта так называемая литература…

  • (no subject)

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

  • (no subject)

    Надо мной все смеются, что я смотрю Киселёва. Но это иногда приносит свои плоды. Вот, например, необыкновенный приступ честности от плачущей карги:…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 18 comments

  • (no subject)

    Зачем-то прослушал «Трудно быть богом». Последний раз читал её в школе. Лишний раз убедился, как же всё-таки быстро эта так называемая литература…

  • (no subject)

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

  • (no subject)

    Надо мной все смеются, что я смотрю Киселёва. Но это иногда приносит свои плоды. Вот, например, необыкновенный приступ честности от плачущей карги:…