catpad (catpad) wrote,
catpad
catpad

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

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


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

voda
eric
nec

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

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

Subscribe

  • The Moth Quest

    Официально открываю новый квест — The Moth Quest AKA Нанюхавшаяся Моль. Участники взяли себе неделю отдыха от предыдущего…

  • Moth Quest

    Вы будете смеяться, но я сделал новый квест — Moth Quest. Под прошлым постом нашлось несколько желающих разгадывать в…

  • Восьмая глава

    Закончил восьмую главу «Хайдеггера и Самовара». Это глава о самых разных языках и о языке вообще, о поэзии, о каббале и о…

  • 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

  • The Moth Quest

    Официально открываю новый квест — The Moth Quest AKA Нанюхавшаяся Моль. Участники взяли себе неделю отдыха от предыдущего…

  • Moth Quest

    Вы будете смеяться, но я сделал новый квест — Moth Quest. Под прошлым постом нашлось несколько желающих разгадывать в…

  • Восьмая глава

    Закончил восьмую главу «Хайдеггера и Самовара». Это глава о самых разных языках и о языке вообще, о поэзии, о каббале и о…