UVa732

UVa732
バックトラックするだけ。

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()

typedef long long int lli;

using namespace std;

stack<char> S;

char buff[1000];

void bt(string s, string t, int idx)
{
  if (s.empty() && t.empty()) {
    for (int i = 0; i < idx; ++i) {
      if (i) cout << ' ';
      cout << buff[i];
    }
    cout << endl;
    return ;
  }
  if (s.size()) {
    buff[idx] = 'i';
    S.push(s[0]);
    bt(s.substr(1), t, idx + 1);
    S.pop();
  } 
  if (t.size() && S.size() && S.top() == t[0]) {
    buff[idx] = 'o';
    S.pop();
    bt(s, t.substr(1), idx + 1);
    S.push(t[0]);
  }
  return ;
}

int main(int argc, char *argv[])
{
  string s, t;
  while (cin >> s >> t) {
    S = stack<char>();
    cout << "[" << endl;
    if (s.size() == t.size()) bt(s, t, 0);
    cout << "]" << endl;
  }
  return 0;
}