В принципе, можно попробовать сделать в один проход.
Для каждой фразы делаем ДКА состояний - чтоб ловить поступающие слова и двигать состояние вперёд, если совпадает с ожидающим следующим словом. Если слова закончились - запоминать найденную позицию и сбрасывать состояние. Если новое слово не совпадает - просто сбрасывать состояние.
А дальше - организуем "игру в лото". Проходимся один раз по тексту от начала до конца и "объявляем" всем участвующим ДКА каждое слово. В конце залезаем в них и получаем списки "выигравших" позиций для каждой фразы.
Это в общем. А дальше можно оптимизировать - например, сравнивать не слова, а хэшики от них.
И не "объявлять" каждому "игроку" каждое слово, а собирать у них множество ожидаемых ими хэшиков - и если текущий попадает в множество - двигать состояния у "выигравших", а у всех остальных - сбрасывать.
Ещё шаг - сделать не одно, а два множества. В одном - хэшики тех, что в начальном состоянии (при сбросе они не меняются -> не нужно читать значения заново). Во втором - "играющие".
Здесь нужно побенчить по сравнению с indexof. Последний внутри себя, конечно, будет работать быстрее, чем аналогичный "самописный", однако на определённых параметрах (совокупность размера входного текста вместе с количеством и размером искомых фраз) уже может вполне его обойти за счёт меньшей сложности.