top coder practice room(practice room1-16)(2001 invi-semi)

         TopCoder practice room (purely for fun)



Problem Statement
    
You have three strings A, B, C. Initially, A is equal to a string init, and B and C are empty. Each character of init is either lowercase 'o' or lowercase 'x'.
Your task in this problem is to transform A from init into goal by applying the following operations to the strings.
If A is not an empty string, remove the leftmost character from A, and add it to the end of B.
If A is not an empty string, remove the leftmost character from A, and add it to the end of C.
If B is not an empty string, remove the leftmost character from B, and add it to the end of A.
If C is not an empty string, remove the leftmost character from C, and add it to the end of A.
You can apply the operations in any order and each operation can be used an arbitrary number of times. Return the minimal number of operations required to finish the task. The constraints guarantee that this is always possible.
Definition
    
Class:
TripleStrings
Method:
getMinimumOperations
Parameters:
string, string
Returns:
int
Method signature:
int getMinimumOperations(string init, string goal)
(be sure your method is public)
    

Constraints
-
init will contain between 1 and 50 characters, inclusive.
-
init and goal will contain the same number of characters.
-
Each character of init and goal will be either lowercase 'o' or lowercase 'x'.
-
The number of 'o' characters in init will be equal to the number of 'o' characters in goal.
Examples
0)

    
"ooxxox"
"xoxoxo"
Returns: 6
One of the optimal solutions is as follows:
initial: A=ooxxox B= C=
use operation 1: A=oxxox B=o C=
use operation 2: A=xxox B=o C=o
use operation 2: A=xox B=o C=ox
use operation 4: A=xoxo B=o C=x
use operation 4: A=xoxox B=o C=
use operation 3: A=xoxoxo B= C=
1)

    
"oooxxoo"
"oooxxoo"
Returns: 0
init and goal are the same, so no operation is required.
2)

    
"ox"
"xo"
Returns: 2

3)

    
"ooxxooxx"
"xxoxoxoo"
Returns: 12

4)

    
"oxxoxxoooxooooxxxoo"
"oxooooxxxooooxoxxxo"
Returns: 16

5)

    
"xxxoxoxxooxooxoxooo"
"oxxooxxooxxoxoxooxo"
Returns: 36

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
///////////////////
I was fooled by this problem as it is quite an intrigue problem. Do you need to count the operations after you find out matching posfix? No, it will always be two times of size as it nevertheless should go to one of buffer before going to destination.
#include <string>

using namespace std;


class TripleStrings
{
public:
int getMinimumOperations(string init, string goal)
{
int posfixStart = findMaxMatchingPrefix(init, goal);

return posfixStart * 2;

}

private:
int findMaxMatchingPrefix(const string& src, const string& dst)
{
int i;
for (i = 0; i < src.size(); i ++)
{
string prefix = src.substr(i);
if (dst.compare(0, prefix.size(), prefix) == 0)
{
break;
}
}
return i;
}

};




back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)