1. To calculate max possible #s, we need to know the longest suffix that is also prefix, and the pattern will be this repeating pattern of prefix * middle * suffix. Note that prefix and suffix may overlap!

  2. DP approach: E(i, typed) = expected # of words to form, where typed letters are typed, and we are matching word[i]

  3. when i is a match, go to E(i+1, typed++) if i < length. Otherwise, it becomes 1 + E(0, typed++)

The final result the sum of all states, since each of them is a distince state

When it doesnt match it goes to E(fallback(i), typed++), where fallback is the longest suffix that ends at i - 1, which is also a prefix => i.e., KMP insight

  1. One important insight is the to use the linearily of expectations.
E (total number of words) = 

E(number of word start at 0+ number of prefix start at 1+...) = 

E(# of word start at 0) + E(# of word start at 1) + ... = 

w * E(# of word start at 0) =  

w * 1 * Pr(a word start at 1)