USACO Problem Crytcowgraphy, Optimizing search.

[meteora]

I am tying to solve this problem:

The cows of Farmer Brown and Farmer John are planning a coordinated escape from their respective farms and have devised a method of encryption to protect their written communications.

Specifically, if one cow has a message, say, "International Olympiad in Informatics", it is altered by inserting the letters C, O, and W, in random location in the message, such that C appears before O, which appears before W. Then the cows take the part of the message between C and O, and the part between O and W, and swap them. Here are two examples:

International Olympiad in Informatics
->
CnOIWternational Olympiad in Informatics

International Olympiad in Informatics
->
International Cin InformaticsOOlympiad W
To make matters more difficult, the cows can apply their encryption scheme several times, by again encrypting the string that results from the previous encryption. One night, Farmer John's cows receive such a multiply-encrypted message. Write a program to compute whether or not the non-encrypted original message could have been the string:

Begin the Escape execution at the Break of Dawn


I am using backtracking to solve this problem, but in the sixth test case:
" BCC execuO the EsCinCaWCCreaOpWtiOn at OCDOcOWaOegCeWtheOW BWoWk of Wwn "
where the answer is actually 0 but my program tries all the possibilities so its timing out.

Here are the optimizations I have tried

1. The part of the encoded message before the first 'C' should match the input string.

2. The part of the encoded message after the last 'W' should match the input string

3. All the substrings in the encoded message between any two letter from 'C','O','W' must be substrings of the input string.

4. At any point of the string the number of Os must be at least as much as the number of Ws and the number of Cs must be at least as much as the number of Os.

I am using C strings (char arrays), I tried switching to C++ and used std::set to store the visited string so that I dont visit them again.

But still the program is timing out on test case 6. I don't thing there is any other algorithm to solve this problem, but I think I am missing some other optimizations.

Here is my code for this problem: http://ideone.com/2fHCM7. Any help would be greatly appreciated.

[Smac89]

Hey man, just thought about it. An algorithm that I think works is to find the last 'C' in the phrase, find the next 'O' directly after last 'C' and find next 'W' directly after last 'O'. Do the replace thing and do it again until you can't find anymore of the letters. I tried it with notepad and the above text and was able to get rid of all 'C', 'O', 'W', but the message I got in the end was garbled nonsence. I will try making a program and see if I get something else

E: Here is a program to find last of the placement of a character since algorithm lib doesn't have one

template <class forwarditer, class constIter>
forwarditer find_last_of(forwarditer first, forwarditer last, constIter myChar)
{
   forwarditer prev = first;
   while(first != last)
   {
      if (*first == *myChar)
	 prev = first;
      
      ++first;
   }
   return prev;
}

[Smac89]

#include <iostream>
#include <cstring>

using namespace std;
typedef unsigned uint;

template <class forwarditer>
uint Find_next(forwarditer start, forwarditer end, const char* MC)
{
    uint _T(0);
    while ((start != end) && *start++ != *MC)
        ++_T;
    return _T;
}

int main()
{
    string message = "International Olympiad in Informatics";
    string encryption, G, H;
    getline(cin, encryption);
    uint s1, s2, s3, numDecode = 0, sixP;
    
    
    while (++numDecode)
    {
        s1 = encryption.find_last_of("C");
        if (s1 == (uint)(-1))
            break;
        encryption.replace(encryption.begin()+s1, encryption.begin()+s1+1, "");
        
        s2 = Find_next(encryption.begin() + s1, encryption.end(), "O");
        encryption.replace(encryption.begin()+s1 + s2, encryption.begin()+s2 + s1 +1, "");
        H = encryption.substr(s1, s2);
        
        s3 = Find_next(encryption.begin() + s2 + s1, encryption.end(), "W");
        encryption.replace(encryption.begin()+s3+s2+s1, encryption.begin()+s3+s2+s1+1, "");
        G = encryption.substr(s1+s2, s3);
        sixP = encryption.length();
        
        if (s2 == sixP || s3 == sixP)
            break;
        
        encryption.insert(s1, G);
        encryption.replace(encryption.begin()+s1+s3, encryption.begin()+s1+s2 +s3, "");
        encryption.insert(s1+s3, H);
        encryption.replace(encryption.begin()+s1+s3+s2, encryption.begin()+s1+s2 +s3+s3, "");
        
    }
    //cout << endl << encryption << endl;
    cout << endl << numDecode-1 <<  " " << (encryption == message ? 1 : 0) << endl;
}