String searching, where we allow characters to almost-match
You're looking for all instances of $Q$ as a substring of $T$, except that two symbols are still considered to match even if they differ by one, so this is basically a generalization of substring search (string matching).

This particular problem can be solved efficiently using convolution methods.  The running time will be something like $O(n \lg n)$, times some small factors.  Let me outline the algorithm, and then explain why it works.

The algorithm

Step 1: We will construct binary strings $T' \in \{0,1\}^{6n}$, $Q' \in \{0,1\}^{6k}$, with a special property:


If index $i$ is good-for-all, then there are $\ge k$ indices $j$ where both $T'_j$ and $Q'_{j+6i}$ are 1.
If index $i$ is not good-for-all, then with probability at least $1/2$, there are $&lt; k$ indices $j$ where both $T'_j$ and $Q'_{j+6i}$ are 1.


Let me outline how to construct $T',Q'$.  First, pick a random hash function $h:\Sigma \to \{1,2,\dots,6\}$.  Next, define a code $C_T:\Sigma \to \{0,1\}^6$ like this: $C_T(x)$ is a 6-bit string that is 1 at index $h(x)$ and 0 at all other positions.  Also, define a code $C_Q:\Sigma \to \{0,1\}^6$ as follows: $C_Q(x)$ is a 6-bit string that is 1 at indices $h(x)$, $h(x-1)$, and $h(x+1)$, and 0 at all other positions.

Finally, define the binary string $T'$ to be the concatenation of codewords

$$T' = C_T(T[0]) C_T(T[1]) \cdots C_T(T[n-1]),$$

and similarly $Q'$ to be the concatenation of codewords

$$Q' = C_Q(Q[0]) C_Q(Q[1]) \cdots C_Q(Q[k-1]).$$

You can check that these two strings satisfy the properties above.

Step 2: We will use convolution (polynomial multiplication) to find all indices that are good-for-all.  Define polynomials $T(x),Q(x)$ from the binary strings $T',Q'$ as follows:

$$\begin{align*}
T(x) &amp;= \sum_j T'_j x^j\\
Q(x) &amp;= \sum_j Q'_j x^{6k-1-j}
\end{align*}$$

Multiply these two polynomials to get the polynomial $P(x) = T(x) Q(x)$.  Let $p_i$ be the coefficient of $x^i$ in $P(x)$, so that $P(x) = \sum_i p_i x^i$.

We have the following nifty property: $p_{6k-1-6i}$ counts the number of indices $j$ where both $T'_{j}$ and $Q'_{j+6i}$ are 1.  Thus, we can immediately read off a set of "suggested" indices that are "suggested good-for-all".  Every index that is actually good-for-all will appear in that set, and every non-good-for-all index has at most a probability $1/2$ of appearing in the set of "suggested" indices.

Step 3: Repeat Steps 1 and 2 80 times, and keep only those indices that are suggested in every iteration.  Output that list.

Correctness

All of the good-for-all indices will remain and appear in the output.  Also, there's at most a $n/2^{80}$ probability that any non-good-for-all index survives all 80 iterations.  This probability is small enough as to be negligible.

Running time

The running time of this algorithm is dominated by the time to multiply two polynomials of degree $6n,6k$.  Assuming $n \ge k$, this running time is basically $O(n \lg n)$ (ignoring log-log factors) using standard techniques.

In practice there are a number of ways one could optimize this further.  For instance, we can often stop early without doing all 80 iterations: once the set of surviving suggested indices is small enough, we can just check each one directly and output only the correct ones.

Other approaches

Since your problem is a generalization of string matching, you could also look at other algorithms for string matching and see if any of those techniques can be generalized to your situation.  For instance:


It would be straightforward to adapt finite automaton based search methods: you can build an automaton based on $Q$ that accepts all strings that would match $Q$ as a substring (where "match" allows two similar characters to be treated as matching).  Building such a DFA might be very slow, but once you have the DFA, testing whether $T$ is a match can be done very fast -- in linear time.
It might be possible to adapt the Knuth-Morris-Pratt algorithm to your situation.  It might take some thought to work out the details, but if it works out, you might get a linear-time algorithm, i.e., $O(n)$ running time.
Also, take a look at Boyer-Moore.


I would especially suggest you take a look at KMP -- it looks plausible to me that this might yield a viable algorithm.