Как быстро на c# искать в строке массив строк?
Прошу прощение за некропостинг, но есть гораздо более простое решение, чем Ахо-Корасики =)string[] array = { "тест1", "тест2", "тест3", "тест4" };

if (new Regex(string.Join("|", array.Select(Regex.Escape))).IsMatch(line))
{
    // do work
}
Я не нашел точной информации, но, похоже, что string.IndexOf использует простоейший алгоритм поиска подстроки, который работает за O(nm). (n - длина исходной строки, m - длина образца).
А поскольку у вас еще p образцов - получаем кубическую сложность.
Самый простой вариант в данном случае - использовать другой алгоритм поиска подстроки. Вообще, алгоритмов поиска подстроки великое множество. Разные алгоритмы с одинаковой асимптотикой могут очень-по разному себя проявлять на различных данных. В любом случае, стоит попробовать разные варианты, чтобы определить какой алгоритм будет быстрее в вашем случае. 
Но, на первый взгляд мне кажется, что вам вполне подойдет алгоритм Ахо—Корасик