Я не нашел точной информации, но, похоже, что string.IndexOf использует простоейший алгоритм поиска подстроки, который работает за O(nm). (n - длина исходной строки, m - длина образца).
А поскольку у вас еще p образцов - получаем кубическую сложность.
Самый простой вариант в данном случае - использовать другой алгоритм поиска подстроки. Вообще, алгоритмов поиска подстроки великое множество. Разные алгоритмы с одинаковой асимптотикой могут очень-по разному себя проявлять на различных данных. В любом случае, стоит попробовать разные варианты, чтобы определить какой алгоритм будет быстрее в вашем случае.
Но, на первый взгляд мне кажется, что вам вполне подойдет алгоритм
Ахо—Корасик 
