[Iska]

seriych, у Кнута смотрели — что он говорит по этому поводу?

[User001]

Или можно объединить все строки из M в одну, уставив какой-то символ-разделитель между каждой строкой и уже тогда применять другой алгоритм? Имеет ли это смысл, если строки в S всё равно короткие и найти надо для каждой? »

Если string::find, то сложность Unspecified, but generally up to linear in length()-pos times the length of the sequence to match (worst case).

Если у вас много памяти, то можно попробовать разбить все строки из M на подстроки и в map, потом уже по нему искать. Это только идея

[seriych]

у Кнута смотрели — что он говорит по этому поводу? »

Нет, не советовался с ним

[Iska]

Попробуйте. Найдёте полезное — нам расскажете.