Waiting time problem for an almost perfect match

Given sequences of finite-state trials, an almost perfect match means that there exists at least k-1 matches between any subsequences of size k in each sequence. Let X1,X2,... be a sequence of {0,1}-valued Markov dependent random variables each resulting in either a match (Xi=1) or mismatch (Xi=0) for i=1,2,... . An explicit expression of the probability generating function of the waiting time for the first occurrence of an almost perfect match is derived. Numerical examples are also given.