挺早的时候写的。那个时候还不知道C的读入效率比C++高，用的还是vector。

/* source:  zju 1004   */
/* algo:  dfs                */
/* date:  2006/5/17     */
/* author:  Crux.D      */

#include <iostream>
#include <fstream>
#include <string>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

string str0, str1;
stack<char> cs;
vector<char> cv;
int l;

void prints()
{
 for(int i = 0; i < cv.size(); i ++)
 {
  cout << cv[i] << " ";
 }
 cout << endl;
}

void dfs(int ii, int oi)
{
 if(ii == l && oi == l)
  prints();
 if(ii + 1 <= l)
 {
  cs.push(str0[ii]);
  cv.push_back('i');
  dfs(ii + 1, oi);
  cs.pop();
  cv.pop_back();
 }
 if(oi + 1 <= ii && oi + 1 <= l && cs.top() == str1[oi])
 {
  char tc = cs.top();
  cs.pop();
  cv.push_back('o');
  dfs(ii, oi + 1);
  cs.push(tc);
  cv.pop_back();
 }
}

int main()
{ 
 //ifstream cin("in.txt");
 while(cin >> str0 >> str1)
 {
  l = str0.length();
  string t1 = str0, t2 = str1;
  sort(t1.begin(), t1.end()), sort(t2.begin(), t2.end());
  cout << "[" << endl;
  if(t1 == t2)
  {
   dfs(0, 0);
  }
  cout << "]" << endl;
 }
 return 0;
}

评论