题目连接 http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1317
题目大意
如何根据一系列堆栈操作实现回文构词法呢？有两种堆栈的操作，将单词TROT转换成TORT。
i代表入栈，o代表出栈。对给定的单词对，编程实现堆栈操作，将第一个单词转换为第二个单词。
有多行输入。每两行的第一个是源单词（不包括换行符），第二行是目标单词（也不包括换行符）。由文件结束符标志输入结束。
对每对单词，有多种有效的方法从源单词产生目标单词，将每种方法的i和o操作排序输出，并以[]分隔。排序的方法是字典序。每个i和o之后都有一个空格。
#include<stdio.h>
#include<string.h>#define M 101
char s[M], t[M];
char a[2*M]; //存放i，o。
int len;
char stack[M]; ////count_i用来记录i的个数.//count_o用来记录o的个数.
void dfs(int tmp, int count_i, int count_o)
{if(tmp == 2*len) {int k = 0;for(int i = 0, j = 0, top = 0; i < tmp; i++) {if(a[i] == 'i') {stack[top++] = s[j++];} else if(a[i] == 'o' && stack[top-1] == t[k]) {top--;k++;} else {return;}}if(k == len) {for(int i = 0; i < tmp; i++) {printf("%c ", a[i]);}printf("\n");}return;}//如果i的个数等于字符串的长度，那么接下来只能输入o。if( count_i == len ) { a[tmp] = 'o';dfs(tmp+1, count_i, count_o+1);//如果i的个数等于0或者i的个数减o等于0，那么接下来只能输入i。} else if(count_i == 0 || count_i - count_o == 0) { a[tmp] = 'i';dfs(tmp+1, count_i+1, count_o);} else {a[tmp] = 'i';dfs(tmp+1, count_i+1, count_o);a[tmp] = 'o';dfs(tmp+1, count_i, count_o+1);}
}int main()
{while(scanf("%s %s", s, t) != EOF) {printf("[\n");len = strlen(s);if(len != strlen(t)) {printf("]\n");continue;}a[0] = 'i';dfs(1, 1, 0);printf("]\n");}return 0;
}
这个代码效率有点低。。。
在哈理工的oj上跑了500多ms，别人都是0ms过的。。。
惭愧--!