[C++] Число вхождений подстроки в строку.

[Константин01]

Найти число вхождений подстроки в строку. (C++)

В общем случае мы используем алгоритм КМП, однако что делать если паттерн может содержать знак "?", который означает любой символ или его отсутствие?

[Dekay]

Ну а обычный поиск за квадрат по времени не пройдет?

[Константин01]

Нет.

Ограничение O(n+m+Z)

где,

n - длина шаблона
m - длина текста
Z - длина строки между знаками вопроса.

[Dekay]

Стоп.
Знаки вопрос стоят только в одном месте непрерывно?

[Константин01]

Исходя из условия задачи, я думаю, что знаки могут быть расположены в произвольном порядке,

например,

"abc??ab" или "ab?ab?ac".

[Dekay]

Сообщение от Константин01

Исходя из условия задачи, я думаю, что знаки могут быть расположены в произвольном порядке,

Какого условия?
Можно его увидеть? Именно адекватное, красивое условие, а не вашу интерпретацию с кмп.
Потому что я не понимаю какие строки даны <chars><?><chars> или <chars>?<chars>?<chars> или еще какие-то

[Константин01]

Шаблон поиска задан строкой длины m, в которой кроме обычных символов могут встречаться символы “?”.
Найти позиции всех вхождений шаблона в тексте длины n. Каждое вхождение шаблона предполагает, что
все обычные символы совпадают с соответствующими из текста, а вместо символа “?” в тексте встречается
произвольный символ.
Время работы - O(n + m + Z), где Z - общее -число вхождений подстрок шаблона “между вопросиками” в
исходном тексте. m ≤ 5000, n ≤ 2000000.