After reading some chapters of "Analytic Combinatorics" by Flajolet and Sedgewick (2009), I have the following problem that I am thinking about regarding patterns and overlaps:
First, to introduce the idea: Let us consider a finite set of symbols $\mathcal{A}$, called alphabet, with cardinality $m$. A word $W$ is a sequence of $n$ symbols from the alphabet, that is, $W=(w_0,w_1,\cdots, w_{n-1}) \in \mathcal{A}^{n}.$
The problem is: how many are the configurations of word W over the alphabet $\mathcal{A}$, which does not contain a pattern $\mathfrak{p}$ of size $k$ starting from the second coordinate, that is, if the pattern appears from the first coordinate, this is counted like a "non-appearance".
For example, calling this desired number of configurations $s_j$ and considering the pattern $\mathfrak{p}$ = 10101. If occurs $$(w_0,w_1,w_2,w_3,w_4,\cdots,w_{j-1},\cdots,w_ {n-1})=(1,0,1,0,1,\cdots,0, \cdots,0)$$ I consider it as a "non-appearance"
I tried to manipulate the generating function of proposition I.4 of the book, which counts from the first coordinate, however, I have many doubts as to whether the overlapping of the word actually prevents some details that at the moment I did not understand for sure. Maybe there is another simpler method that you are not realizing.