1143.字母转换
时限：1000ms 内存限制：10000K 总时限：3000ms
描述
通过栈交换字母顺序。给定两个字符串，要求所有的进栈和出栈序列（i表示进栈，o表示出栈），使得字符串2在求得的进出栈序列的操作下，变成字符串1。输出结果需满足字典序。例如TROT 到 TORT:
[
i i i i o o o o
i o i i o o i o
]
输入
给定两个字符串，第一个字符串是源字符串，第二个字符是目标目标字符串。
输出
所有的进栈和出栈序列,输出结果需满足字典序
输入样例
madam adamm bahama bahama long short eric rice
输出样例
[ 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 ]
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
stack<char>stack1;
char s1[1000],s2[1000],s3[1000],s4[1000],a[1000];
int length1;
int issubstr(char a[],char b[])//判断b是否是a的子串
{
int k=strlen(b);
for(int i=0;i<k;i++)
{
if(a[i]!=b[i])return 0;
}
return 1;
}
void dfs(int i,int j,char s3[])
{
int m;
if(strcmp(s2,s3)==0&&stack1.empty()&&j==length1)
{
for( m=0;m<i-1;m++)
{
cout<<a[m]<<" ";
}
cout<<a[m];
cout<<endl;
}
if(j<length1)//入栈
{
a[i]='i';
stack1.push(s1[j]);
dfs(i+1,j+1,s3);
stack1.pop();//恢复
}
if(!stack1.empty())//出栈
{
char s4[1000];
memset(s4,0,sizeof(s4));
strcpy(s4,s3);
char top=stack1.top();
int length3=strlen(s3);
s4[length3++]=top;
if(issubstr(s2,s4))
{
a[i]='o';
stack1.pop();
dfs(i+1,j,s4);
stack1.push(top);//恢复
}
}
}
int main()
{
while( cin>>s1>>s2)
{
memset(a,0,sizeof(a));
length1=strlen(s1);
cout<<"["<<endl;
dfs(0,0,s3);
cout<<"]"<<endl;
}
return 0;
}