Append |
Consider the following encoding scheme used in one famous compresion algorithm. Suppose we will code only sequences of lower case letters. Each such sequence of characters can be encoded to a sequence of pairs (p_{i}, r_{i}), where is an integer and r_{i} is either a character (if p_{i} = 0) or an integer greater than zero and less or equal than p_{i} (if p_{i} > 0).
We describe now the decoding procedure for our encoding scheme. Let (p_{1}, r_{1}), (p_{2}, r_{2}), be a code of a sequence. We get the sequence as follows: we take successively individual pairs of the code. If p_{i} = 0 then r_{i} is a character and we simply add r_{i} to the end of already decoded sequence. If p_{i} > 0 then r_{i} is an integer, , and we add to already decoded sequence r_{i} letters from this sequence starting at the position p_{i} places before the end.
For example, consider the sequence of pairs (0 a), (1, 1), (0, b), (3, 3), (3, 3), (3, 2), (0, c). Decoding (0, a) we get a. Decoding (1, 1) we get aa. (0, b) adds b getting aab. (3, 3) will add aab, so now we have aabaab. Next pair (3, 3) will again add aab so we have aabaabaab. (3, 2) will add aa, so our sequence is aabaabaabaa and (0, c) adds c. So the decoded sequence is aabaabaabaac. Note that in general for a given w it can exist more such sequences of pairs.
Let u, v be some sequences. By uv we will understand the sequence created by appending of the sequence v to the end of sequence u. Let C_{w} be a sequence of pairs which encodes a sequence of lowercase letters w. Suppose we have given a sequence of pairs C_{w}. The question is how many possibilities does exist for expressing the sequence C_{w} in the form C_{u} C_{v} where u, v are sequences satisfying the equation w = uv and neither u nor v is empty. Write a program that will answer this question.
0 a 1 1 0 b 3 3 3 3 3 2 0 c
1