generator – regionals 2015 asia-hangzhou

We generate a random string by generating a sequence of random characters and concatenating them together. Each character is chosen independently from the first n letters in the English alphabet with equal probability. Only capital letters are used in this problem. The generation is stopped as soon as a specific pattern occurs in the random string. Your task is to predict the expected length of the generated string.

• 1 <= T <= 10.
• 1 <= n <= 26.
• The length of any pattern will not exceed 12.

• For any string S, define the function state(S) as the maximal length of the prefix of pattern which is also a suffix of the current string at the same time.
• If the pattern has length L, then the state of any string is a number between 0 and L.
• We know that L is a final state.
• Let’s define f[i] as the expected number of steps from state i to state L.
• Then we have f[i] = 1+ 1/n(f[a(1,1)]+f[a(1,2)]+…+f[a(1,n)]), where a(i,j) is the state of the new string after concatenating the current string and the j-th letter together.
• Thus, the answer is f[0].

• We can use brute-force to compute a(i,j).