Fast algorithm for scoring a sequence
The problem can be solved at least in $O(M \cdot T \log T)$ which is theoretically better, but may be slower than $O(M\cdot T\cdot L)$ in practice if $L$ is comparable to $\log T$.  

Let's show how to find a score of each $v_i$ independently in $O(T \log T)$. For any (possibly gapped) string $W = w_0 w_1 \ldots w_{n-1}$ define two polynomials $zeros_W(x)$ and $ones_W(x)$ as follows:

$$ zeros_W(x) = \sum_{i=0}^{n-1} [w_i = &#39;&#39;0&#39;&#39;]x^i$$
$$ ones_W(x) = \sum_{i=0}^{n-1} [w_i = &#39;&#39;1&#39;&#39;]x^i$$

where $[P]$ is Iverson notation. 

For example, $zeros_{01...01}(x) = 1 + x^5$, $ones_{01...01}(x) = x + x^6$, $zeros_{0001100}(x) = 1+x+x^2+x^5+x^6$ and $ones_{0001100}(x) = x^3 + x^4$.

Then compute coefficients of the following polynomial $$c(x) = zeros_S(x) \cdot ones_{rev(v_i)}(x) + ones_{S}(x) \cdot zeros_{rev(v_i)}(x) = \sum_{j}c_j x^j$$ where $rev(W) = w_{n-1} \ldots w_1 w_0$ is just reversed $W$. It's easy to see that $c_{L-1+k}$ will be equals exactly to the difference between $s_k s_{k+1} \ldots s_{k+L-1}$ and $v_i$. For example, for $S=&#39;&#39;0100&#39;&#39;$ and $v_i = &#39;&#39;10&#39;&#39;$ $c(x)$ will be equal to $(1+x^2+x^3)\cdot x + x \cdot 1 = 2x + x^3 + x^4$ which gives us all interesting differences (2, 0, 1) so we can calculate score in linear time. Thus the problem is reduced to polynomial multiplication, which can be done in $O(T \log T)$ using FFT.

The possible disadvantage of such approach is that FFT has essential constant hidden in its big-O, so using $O(T^{1.585})$ Karatsuba multiplication or something similar may work better in practice for not very large $T$.