6243: Colorful Stones
题目描述
There are two sequences of colorful stones. The color of each stone is one of red, green, or blue. You are given two strings s and t. The i-th (1-based) character of s represents the color of the i-th stone of the first sequence. Similarly, the i-th (1-based) character of t represents the color of the i-th stone of the second sequence. If the character is "R", "G", or "B", the color of the corresponding stone is red, green, or blue, respectively.
Initially Squirrel Liss is standing on the first stone of the first sequence and Cat Vasya is standing on the first stone of the second sequence. You can perform the following instructions zero or more times.
Each instruction is one of the three types: "RED", "GREEN", or "BLUE". After an instruction c, the animals standing on stones whose colors are c will move one stone forward. For example, if you perform an instruction «RED», the animals standing on red stones will move one stone forward. You are not allowed to perform instructions that lead some animals out of the sequences. In other words, if some animals are standing on the last stones, you can't perform the instructions of the colors of those stones.
A pair of positions (position of Liss, position of Vasya) is called a state. A state is called reachable if the state is reachable by performing instructions zero or more times from the initial state (1, 1). Calculate the number of distinct reachable states.
The input contains two lines. The first line contains the string s (1≤|s|≤106). The second line contains the string t (1≤|t|≤106). The characters of each string will be one of "R", "G", or "B".
Print the number of distinct reachable states in a single line.
Please, do not write the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.
RBR
RGG
5
RGBB
BRRBRR
19
RRRRRRRRRR
RRRRRRRR
8
In the first example, there are five reachable states: (1, 1), (2, 2), (2, 3), (3, 2), and (3, 3). For example, the state (3, 3) is reachable because if you perform instructions "RED", "GREEN", and "BLUE" in this order from the initial state, the state will be (3, 3). The following picture shows how the instructions work in this case.
