catpad (catpad) wrote,
catpad
catpad

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

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


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

voda
eric
nec

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

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

Subscribe

  • (no subject)

    Читаю интереснейшую книгу «Beyond: The Astonishing Story of the First Human to Leave Our Planet and Journey into Space» by Stephen Walker. Там все…

  • Community

    Кинопоиск сделал отличный обзор «Community» и этим напомнил мне о великом сериале. Тут дело такое. Дэн Хармон, прежде чем сделать «Rick &…

  • (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)

    Читаю интереснейшую книгу «Beyond: The Astonishing Story of the First Human to Leave Our Planet and Journey into Space» by Stephen Walker. Там все…

  • Community

    Кинопоиск сделал отличный обзор «Community» и этим напомнил мне о великом сериале. Тут дело такое. Дэн Хармон, прежде чем сделать «Rick &…

  • (no subject)

    Так называемый министр иностранных дел Лавров разразился мракобесной статьей, над которой все смеются из-за того, что там упоминаются некие…