题目传送门
/*
stack 容器的应用: 要求字典序升序输出,所以先搜索入栈的
然后逐个判断是否满足答案,若不满足,回溯继续搜索,输出所有符合的结果
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 1e4 + ;
const int INF = 0x3f3f3f3f;
string s1, s2;
int len;
stack<char> S;
vector<char> V;
void DFS(int push, int pop)
{
if (push == len && pop == len)
{
for (int i=; i<V.size (); ++i)
cout << V[i] << " ";
cout << endl;
}
if (push + <= len) //入栈
{
S.push (s1[push]);
V.push_back ('i');
DFS (push+, pop);
S.pop ();
V.pop_back ();
}
if (pop + <= push && pop + <= len && S.top () == s2[pop]) //出栈
{
char ch = S.top ();
S.pop ();
V.push_back ('o');
DFS (push, pop+);
S.push (ch);
V.pop_back ();
}
}
int main(void) //ZOJ 1004 Anagrams by Stack
{
//freopen ("ZOJ_1004.in", "r", stdin);
while (cin >> s1 >> s2)
{
V.clear ();
while (!S.empty ()) S.pop ();
len = s1.length ();
cout << "[" << endl;
DFS (, );
cout << "]" << endl;
}
return ;
}
/*
[
i i i i o o o i o o
i i i i o o o o i o
i i o i o i o i o o
i i o i o i o o i o
]
[
i o i i i o o i i o o o
i o i i i o o o i o i o
i o i o i o i i i o o o
i o i o i o i o i o i o
]
[
]
[
i i o i o i o o
]
*/