<s>[INST] Count number of exact matching sequences Consider all pairs of binary strings $P$ and $T$. Let the length of $P$ be $n$ and the length of $T$ be $2n-1$.  For each such pair, we can check if $P$ is exactly equal to each of the $n$ substrings of $T$ in order from left to right and output a sequence representing these results. For example:
$$P = 11011, T = 111011011$$
gives an output sequence:
$$01001$$
where $1$ represents an exact matching and $0$ represents a mismatch.
If we iterate over all possible pairs $P$, $T$ we can count how many distinct sequences we get from the outputs.  For $n = 2, \dots, 9$ we get 


*

*$n = 2$ gives 4

*$n = 3$ gives 8

*$n = 4$ gives 14 

*$n = 5$ gives 23 

*$n = 6$ gives 34 

*$n = 7$ gives 49

*$n = 8$ gives 66

*$n = 9$ gives 87



Is it possible to give a formula for this count or alternatively to give an asymptotic approximation?

 [/INST] Lemma. Let $R = R(P, T)$ be an output sequence for given strings $P$ and $T$ of length $n$ and $2n - 1$ correspondingly. Then
$$R = \underbrace{00\ldots\ldots\ldots\ldots\ldots\ldots0}_{\text{non-negative number of zeros}}\underbrace{1\underbrace{0\ldots0}_{\text{$k - 1$ zeros}}1\underbrace{0\ldots0}_{\text{$k - 1$ zeros}}1\ldots 1\underbrace{0\ldots0}_{\text{$k - 1$ zeros}}1}_{\text{non-negative number of ones}}\underbrace{00\ldots\ldots\ldots\ldots\ldots\ldots0}_{\text{non-negative number of zeros}}$$
for some positive integer $k$. (In other words, the distance between any two neighbouring ones in $R$ is the same.)
Proof. Suppose
$$R = \underbrace{\ldots\ldots\ldots}_{\text{whatever}}1\underbrace{00\ldots0}_{\text{$k - 1$ zeros}}1\underbrace{00\ldots0}_{\text{$\ell - 1$ zeros}}1\underbrace{\ldots\ldots\ldots}_{\text{whatever}}$$
for some positive integers $k \ne \ell$.
Let $k < \ell$, otherwise we can reverse all $P$, $T$ and $R$.
Let $P = a_0a_1\ldots a_{n - 1}$ where $a_i$ are symbols. Let $d = \gcd\{\,k, \ell\,\}$. Then
$$T = T_1P_0P_1\ldots P_mT_2,$$
where $T_i$ and $P_i$ are strings such that $P = P_0 P_1 \ldots P_{x - 1}P'_x$, $|P_0| = |P_1| = \ldots = |P_{m - 1}| = d$, $0 \le |P_m| < d$ and $P'_x = P_m$ is a prefix of $P_x$.
(Here $AB$ means concatenation of strings $A$ and $B$.)
Let $K = \frac{k}{d}$ and $L = \frac{\ell}{d}$. Then $P_i = P_{i + K}$ for $0 \le i < m - K$ and
$P_i = P_{i + L}$ for $0 \le i < m - L$. Also $\gcd\{\,K, L\,\} = 1$.
So $P_0 = P_{K} = P_{2K} = \ldots = P_{yK}$ for $(y - 1)K < L \le yK$.
If $K \mid L$ then it is easy to see that $P$ is prefix of $P_0P_1\ldots P_x = P_1P_2 \ldots P_{x+1}$, therefore $R$ misses at least one 1.
Then $(y - 1)K < L < yK$ and $P_0 = P_{yK - L} = P_{yK - L + K} = \ldots$. Iterating this process we get $P_0 = P_1 = \ldots = P_{m - 1}$ and $P_m$ is a prefix of $P_0.$ Therefore $R$ misses at least one 1, and this contradiction proves lemma. $\square$
It is easy to see that every $R$ described in the condition of lemma is achievable, so lemma describes all $R$ possible.
To compute the number of such sequences it is better to count sequences of all 0's and sequences with one 1 and then for all $k$ find the nubmer of sequences with at least two 1's:
$$1 + n + \sum_{k = 1}^{n - 1} \sum_{r = 0}^{k - 1}\binom{\left\lceil\frac{n - r}{k}\right\rceil}{2}.$$
Here $k$ is the distance between ones, $r$ is a remainder of (zero-based) position number of the first 1 modulo $k$ and $\binom{\left\lceil\frac{n - r}{k}\right\rceil}{2}$ is the number of ways to choose the first and the last 1's.
P. S. It is possible to show that asymptotics of this functions is $\frac12n^2\ln n$.
Let $f(n)$ be the desired number of sequences. Using inequality $x \le \lceil x \rceil < x + 1$ we get
$$1 + n + \sum_{k = 1}^{n - 1} \sum_{r = 0}^{k - 1}\binom{\frac{n - r}{k}}{2} \le f(n) < 1 + n + \sum_{k = 1}^{n - 1} \sum_{r = 0}^{k - 1}\binom{\frac{n - r}{k} + 1}{2}\\
\sum_{k = 1}^{n - 1} \sum_{r = 0}^{k - 1}\frac12\cdot\frac{n - r}{k}\left(\frac{n - r}{k} - 1\right) \le f(n) - 1 - n < \sum_{k = 1}^{n - 1} \sum_{r = 0}^{k - 1}\frac12\cdot\frac{n - r}{k}\left(\frac{n - r}{k} + 1\right)\\
\sum_{k = 1}^{n - 1} \sum_{r = 0}^{k - 1}\frac{1}{k^2}(n - r - k)(n - r) \le 2(f(n) - 1 - n) < \sum_{k = 1}^{n - 1} \sum_{r = 0}^{k - 1}\frac{1}{k^2}(n - r)(n - r + k)\\
\sum_{k = 1}^{n - 1} \frac{1}{k^2}\sum_{r = 0}^{k - 1}(n^2 + O(kn)) \le 2(f(n) - 1 - n) < \sum_{k = 1}^{n - 1} \frac{1}{k^2}\sum_{r = 0}^{k - 1}(n^2 + O(kn))\\
\sum_{k = 1}^{n - 1} \frac{1}{k^2}(kn^2 + O(k^2n)) \le 2(f(n) - 1 - n) < \sum_{k = 1}^{n - 1} \frac{1}{k^2}(kn^2 + O(k^2n))\\
n^2\sum_{k = 1}^{n - 1} \left(\frac{1}{k} + O\left(\frac1n\right)\right) \le 2(f(n) - 1 - n) < n^2\sum_{k = 1}^{n - 1} \left(\frac{1}{k} + O\left(\frac1n\right)\right)\\
n^2\ln n \sim n^2(H_{n - 1} + O(1)) \le 2(f(n) - 1 - n) < n^2(H_{n - 1} + O(1)) \sim n^2\ln n.
$$
Thus $f(n) \sim \frac12n^2\ln n$.
</s>