Let's keep bitsets bit_a, bit_b, \ldots, bit_z, where corresponding bitset has ones only at positions where his letter is present. Updating these bitsets after queries of type is trivial, let's see how to deal with queries of type .
Suppose that we received a string p_1p_2\ldots p_k as the query string. Then consider bitset bit_{p_1} \text{AND} (bit_{p_2} > >1) \text{AND} (bit_{p_3} > >2) \ldots \text{AND} (bit_{p_k} > >(k-1)) (here by we denote the shift of bitset to the left by , and by — binary AND of the bitsets.
Clearly, in this bitset we will have ones only at such positions that s_{pos} = p_1, s_{pos+1} = p_2, \ldots, s_{pos+k-1} = p_k, which is precisely what we need. To find the number of the ones set, use bitset.count().
Total complexity would be O(\frac{n(q + sum(|p|))}{64}), which passes comfortably.