La tarea 5 se puede resolver de una manera muy similar a como se resuelve la tarea 4 (sin usar memoria dinámica ni std::vector, si se les llegara a ocurrir cómo, están en libertad de hacerlo así), pero hay una forma más elegante.

Cuando en clase les sugerí que usaran std::vector (pero no les dije para qué), no me refería a que usaran std::vector para leer la cadena (la cadena tiene a lo mucho 1000000 caracteres más el nulo, lo cual perfectamente se puede representar con un arreglo de char en la pila). La idea que les sugiero es la siguiente: si me dan la cadena "gatitoloco" entonces puedo construir la representación que se conoce como índice invertido: cada caracter tiene una lista de las posiciones en las que aparece dicho caracter. 

   // En este ejemplo considero únicamente letras minúsculas; la cadena también puede tener letras mayúsculas y dígitos.
a: { 1 }
b: { }
c: { 8 }
d: { }
e: { }
f: { }
g: { 0 }
h: { }
i: { 3 }
j: { }
k: { }
l: { 6 }
m: { }
n: { }
o: { 5, 7, 9 }
p: { }
q: { }
r: { }
s: { }
t: { 2, 4 }
u: { }
v: { }
w: { }
x: { }
y: { }
z: { }

Cuando les llega una consulta, pueden ir directamente a la lista de ese caracter ignorando todas las demás listas. Ojo: aún haciendo eso, búsqueda lineal no quedará en tiempo.

PD. Lean bien el problema: las consultas son tripletas (C, I, T) donde I es una posición y T es un tamaño a partir de I (no una posición).