一道不错的搜索题
题意：告诉你两个字符串a和b，要求对a进行栈的操作而产生b串，输出操作的顺序，如果有多组输出就按字典序输出。
Sample Input
madam
adamm
bahama
bahama
long
short
eric
rice
Sample Output
[
i i i i o o o i o o
i i i i o o o o i o
i i o i o i o i o o
i i o i o i o o i o
]
[
i o i i i o o i i o o o
i o i i i o o o i o i o
i o i o i o i i i o o o
i o i o i o i o i o i o
]
[
]
[
i i o i o i o o
] 这道搜索题不太好理解，通过输出中间变量来辅助理解，这里是第一个例子
[
0 0 0
1 0 1
2 0 2
3 0 3
4 0 4
5 0 5 //到这里madam全部进入栈中
4 1 5 //5 0 5状态均不符合任何if，退出，由 4 0 4 开始，符合最后一个条件
5 1 6 //符合第二个if，之后不符合任何条件，由4 1 5开始
4 2 6
5 2 7
4 3 7
5 3 8
5 4 9
5 5 10
i i i i o o o i o o
4 4 8
5 4 9
5 5 10
i i i i o o o o i o
2 1 3
3 1 4
4 1 5
5 1 6
3 2 5
4 2 6
5 2 7
4 3 7
5 3 8
5 4 9
5 5 10
i i o i o i o i o o
4 4 8
5 4 9
5 5 10
i i o i o i o o i o
]
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
int n,m,t;
int len1,len2;
int num[];
char s1[],s2[] ;
stack<int> q;
int tot=;
void dfs(int i,int j,int k) //s1的状态，s2的状态，当前栈的元素数目
{
//printf("%d %d %d\n",i,j,k);
if(j==len2)
{
for(i=;i<k;i++)
{
if(num[i]) printf("i ");
else printf("o ");
}
printf("\n");
return;
}
if(i<len1)
{
q.push(s1[i]);
num[k]=;
dfs(i+,j,k+);
q.pop();
}
if(!q.empty()&&q.top()==s2[j])
{
char ss=q.top();
q.pop();
num[k]=;
dfs(i,j+,k+);
q.push(ss);
}
}
int main()
{
int i,j,k;
//freopen("1.in","r",stdin);
while(scanf("%s%s",s1,s2)!=EOF)
{
len1=strlen(s1);
len2=strlen(s2);
printf("[\n");
dfs(,,);
printf("]\n");
}
return ;
}