Generating function for the set of $w$-free words.

Question

Suppose $X$ is an alphabet and $w \in X^n$ is a word over it. Consider a set $P$ of $w$-free words over $X$ (a word is called $w$-free if it does not contain $w$ as a subword). I want to write a generating function for $P$ (by length). I am trying to write some kind of a recurrence relation considering the set $Q$ of words $u$ over $X$ such that $u$ ends with $w$ and $u$ does not contain $w$ as a subword in any other position. But clearly, if we take a word $a \in P$, it does not imply that $aw \in P$, so such a recurrence relation largely depends on $w$. Can you please suggest, is there such a way of deriving the generating function? Any references will be also appreciated.

Answer 1

I recommend you look at the Goulden-Jackson cluster method. See, for example, this answer, which contains references.