Common words between two random strings
Philippe Jacquet · 2007
We investigate the problem of enumerating the words that are common to two random strings. We show that when the source models are memoryless that the number of common words is sublinear in the length of the sequence, and linear when the source models are exactly the same. We draw the same conclusions for the number of common nodes in the associated respective suffix trees.