用到的主要是回溯，递归时先将所有字符放入栈中，在回溯时判断字符是否出栈并记录路径。栈是用字符数组模拟的。

另外这题的输出有点扯，每一行的最后一个i或o后面是有空格的，不需要处理，PE一次。

code:

#include<cstdio>

#include<cstring>

using 

namespace std ;

char str[

50] ;

char bstr[

50], estr[

50], ans[

100] ;

int blen, temp, h, r ;

void dfs(

int bpos, 

int epos, 

int count){

    

if(epos==blen){

        

int i ;

        

for(i=

0; i<count; i++)

            printf(

"

%c 

", ans[i]) ;

        printf(

"

\n

") ;

    }

    

if(bpos<blen){

        str[r++] = bstr[bpos] ;

        ans[count] = 

'

i

' ;

        dfs(bpos+

1, epos, count+

1) ;

        r -- ;

    }

    

if(h!=r&&estr[epos]==str[r-

1]){

        

char a = str[r-

1] ;

        r -- ;

        ans[count] = 

'

o

' ;

        dfs(bpos, epos+

1, count+

1) ;

        str[r++] = a ;

    }

}

int main(){

    

while(~scanf(

"

%s%s

", bstr, estr)){

        blen = strlen(bstr) ;

        h = r = 

0 ;

        printf(

"

[\n

") ;

        dfs(

0, 

0, 

0) ;

        printf(

"

]\n

") ;

    }

    

return 

0 ;}