Anagrams By Stack.cpp

//https://icpcarchive.ecs.baylor.edu/external/23/2301.pdf
#include <bits/stdc++.h>

using namespace std;

set <string> sequences;

int n;
string start, endW;

void generate(string possible, char op, int index)
{
    if(index == 2*start.length())
    {
    	int it = 0;
    	string word;
    	stack <char> s;
    	bool ilegal = false;
    	if(op == 'o')
    	{
    		for(char c: possible)
    		{
    			if(c == 'i' )
    			{
    				if(it < start.length())
    					s.push(start[it++]);
    				else ilegal = true;
    			}
    			else if(c == 'o')
    			{
    				if(!s.empty())
    				{
    					word.push_back(s.top());
    					s.pop();
    				}
    				else
    					ilegal = true;
    			}
    		}
    		//cout << word << " " << endW << endl;
    		if(word == endW and !ilegal)
    		{
    			//cout << possible << endl;
    			sequences.insert(possible);
    		}
    	}
    	return;
    }
    
    possible[index] = op;
    generate(possible, 'o', index+1);
    generate(possible, 'i', index+1);

}
int main()
{
	cin >> n;

	while(n--)
	{
		cin >> start;
		cin >> endW;
		
		string possible = "oooooooo";
		generate(possible, 'o', 0);
		generate(possible, 'i', 0);

		cout << "Output for " << start << " " << endW << endl << "[" << endl;
		for(set<string>::iterator it = sequences.begin(); it != sequences.end(); it++)
		{
			for(int i = 0; i < (*it).length(); i++)
			{
				cout << (*it)[i];
				if(i +1 != (*it).length())
				{
					cout << " ";
				}
			}
			cout << endl;
		}
		cout << "]";
		if(n != 0)
			cout << endl;
		sequences.clear();
	}

	return 0;
}