ICPC and Typos#12870

ICPC and Typos (Editorial)

Let denote the length of the string .

Note that typos of different types produce words with different number of letters, so it's enough the number of possible words that may occur from each type separately, and then add them.

For type it's easy: each letter can be replaced by n-1 other letters, so here we get m(n-1) words.

For type : let's consider strings s_1s_2\ldots s_{i-1}s_{i+1}\ldots s_m for each from to . When are two such strings equal? s_1s_2\ldots s_{i-1}s_{i+1}\ldots s_m = s_1s_2\ldots s_{j-1}s_{j+1}\ldots s_m with i<j if s_i = s_{i+1}, s_{i+1} = s_{i+2}, , s_{j-1} = s_j. In other words, when all letters from s_i to s_j are equal. This implies that the number of distinct words is + the number of such that s_i \neq s_{i+1}.

For type : let's count the number of ways to insert some character. Let the word after inserting it be .

If t_1 \neq s_1, the character different from s_1 must have been inserted before the first position, which gives n-1 words. Otherwise, s_1 = t_1, and we safely assume that we inserted after the first position (even if we inserted s_1 before s_1, we could have inserted it after s_1, and nothing would change. So we can consider t[2:m+1], s[2:m] from now on.

This iterative process would give us (n-1) + (n-1) + \ldots + (n-1) ( times) + (resulting from inserting any letter in the end) different words.