[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, потом уже по нему искать. Это только идея