dfs(0,0);
printf("]\n");
}
return 0;
}
#include
#include
#include
#include
using namespace std;
stack
char s1[100],s2[100],way[200];//s1存给定序列s2存目标序列。way记录操作
int cnt;
void print()//如果搜索到满足条件的方法则输出
{
int i;
for(i=0; i
printf("\n");
}
void dfs(int p1,int p2)//p1表示s1待入栈位置.p2表示s2待匹配位置
{
if(s2[p2]=='\0')//如果目标序列已完全匹配输出答案返回
{
print();
return;
}
char c;
if(s1[p1]!='\0')//如果s1还没有完全进栈按题目要求字典顺序（先进栈后出栈搜索）
{
c=s1[p1];
sta.push(c);
way[cnt++]='i';
dfs(p1+1,p2);
sta.pop();
cnt--;
}
if(!sta.empty())//后出栈（如果栈不为空）开始没判断栈空，结果找了很久bug
{
c=sta.top();
if(c==s2[p2])//注意该处剪枝
{
sta.pop();
way[cnt++]='o';
dfs(p1,p2+1);
cnt--;
sta.push(c);
}
}
}
int main()
{
while(~scanf("%s%s",s1,s2))
{
while(!sta.empty())
sta.pop();
cnt=0;
printf("[\n");
dfs(0,0);
printf("]\n");
}
return 0;
}