Уточнения к задаче

[catpad]

Вижу, что нужно внести уточнения к этой задаче:
1) хитроумные библиотечные функции применять нельзя, иначе теряется весь смысл задачи.
2) N - это длина входной строки, а не размер множества всевозможных подстрок. Сложность алгоритма должа зависеть только от N и не должна зависеть от размера данного множества подстрок (который может быть очень большим).
3) У подстроки в заданном множестве имеется верхняя граница длины (в реальности 20).

Comments

[mopexod.livejournal.com]

не поможет ли тут "трай", не знаю, как это по-английски... дерево сделать из словаря подстрок.

[catpad.livejournal.com]

Видимо, это оно самое и есть, только я не знал, как оно называется. Я его сам придумал, завтра покажу.

[roza.livejournal.com]

Ну учили же...

[catpad.livejournal.com]

Кто учил, а кто прогуливал :)

[ilyabo.livejournal.com]

Правильно я понимаю, что множество строк заранее задано, а на входе алгоритм получает только строку для поиска в ней подстрок, и следовательно, по множеству строк можно вначале один раз построить достаточно сложную структуру данных, в которой легко будет искать подстроки (причем сложность алгоритма построения этой структуры может естественно зависеть от числа строк)?

[catpad.livejournal.com]

Да, всё правильно.