Overlap of words complicates the problem of word counting. The technique of the imbedded Markov chain
(IMC) uses an enlarged state space to recover the Markovian property for the word counting problem. A degenerate word
represents multiple non-degenerate words. An efficient way to decompose a degenerate word according to its overlapping
pattern for implementing IMC is proposed.