zoj1004

#include <iostream>
#include <string>
#include <stack>
#include <fstream>
using namespace std;
char *pSrc = NULL;
char *pDest = NULL;
stack<char> s1;
char res[1000];
int cnt = 0;
void work(){
   if(*pDest == '\0'){
       for(int i = 0; i < cnt; i++){
         cout << res[i] << " ";
	   }
	   cout << endl;
	   return ;
   }
   
      if(*pSrc != '\0'){
  	    s1.push(*pSrc);
	  	pSrc++;
	  	res[cnt] = 'i';
	  	cnt++;
	  	work();
	  	pSrc--;
	  	cnt--;
	  	s1.pop();
   }
   
   if(!s1.empty()){
      if(s1.top() == *pDest){
        char c = s1.top();
		s1.pop();
		res[cnt] = 'o';
        cnt++;
        pDest++;
        work();
        s1.push(c);
        cnt--;
        pDest--;
	  }
   }
}
int main(){
   string strSrc;
   string strDest;
   while(cin >> strSrc >> strDest){
   	 cnt = 0;
     pSrc = const_cast<char *> (strSrc.c_str());
     pDest = const_cast<char *> (strDest.c_str());
     cout << "[" << endl;
	 work();
	 cout << "]" << endl;
   }
   return 0;
}

回溯法，好久没做题了，工作之余抽空做做，练习练习c++和一些基本算法