El 'algoritmo KMP' (de Knuth, Morris y Pratt) es un algoritmo para buscar subacadenas completas, como en tu caso la búsqueda es parcial...  puede ser readaptado para dicha situación.
https://es.wikipedia.org/wiki/Algoritmo_Knuth-Morris-Pratt

Hace ya como 8-9 años edité el algoritmo (en wikipedia) para expresar claramente el funcionamiento (era un galimatías incomprensible) y poner ejemplos más explícitos y paso a paso así como el pseudocódigo del mismo (había ineficientes implementaciones en varios lenguajes).
...fíjate que el algoritmo se compone de dos partes, en la primera se precomputa una tabla de saltos, que acelerarán las búsqueda.

Puede ser aún más aficiente si se conoce previamente que 'SIEMPRE' se darán ciertas condiciones, que si ha de ser universal (por ejemplo, saber que la subcadena a buscar siempre será máyor de x caracteres y si es menor se rechaza).

Aunque igualmente puedes readaptar el algoritmo de Boyer-Moore para el mismo propósito.

Claro la cosa está en si implementas el algoritmo o simplemente lo utilizas desde una librería, en cuyo caso no ha lugar a optimización, si no simples llamadas en un bucle.