{% link 洛谷文章链接,xyx404,https://www.luogu.com.cn/article/sofzxmhd %}
题意简述： #
多组数据。
每组数据给出两个字符串（源字符串和目标字符串），输出所有通过栈操作将源单词转为目标单词的操作字符串（i 表示入栈，o 表示出栈）。
操作字符串按字典序输出。
思路： #
使用 DFS 算法，暴力模拟出栈入栈操作，为了保证按字典序从小到大输出，应该优先模拟入栈操作。因为入栈用字母 i 表示，出栈用字母 o 表示，很明显 i 的字典序比 o 小。
特别注意：本题不允许行末多余空格。
代码： #
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
string st,en;
stack<char>sta;
int lenen;
void dfs(int s,int e,string op/*操作*/){
if(e==lenen){
cout<<op<<"\n";
return;
}
// cout<<op<<"\n";
// i 的 ASCII 码值小于 o 为了保证字典序从小到大，先从小的开始
if(s<st.size()){// 模拟入栈
sta.push(st[s]);
dfs(s+1,e,op+"i ");
sta.pop();// 回溯
}
if(!sta.empty()&&sta.top()==en[e]){
char k=sta.top();
sta.pop();
if(e+1!=lenen)dfs(s,e+1,op+"o ");// 不要问为什么这么写
else dfs(s,e+1,op+"o");// 因为直接 dfs(s,e+1,op+"o ") 会 PE
sta.push(k);
}
return;
}
int main(){
while(cin>>st>>en){
cout<<"[\n";
string a=st,b=en;
lenen=en.size();
sort(a.begin(),a.end());
sort(b.begin(),b.end());
if(a==b)dfs(0,0,"");// 特判类似于样例中的 st=long,en=short 两个字符串字符不一样的情况
cout<<"]\n";
}
return 0;
}