杭电oj 1515题
题目链接：//http://acm.hdu.edu.cn/showproblem.php?pid=1515
#include<stdio.h>#include<string.h>char path[200];int k = 0;void sta(char *s,char *p,char *stackk,int i,int j,int t){ int m = 0; char stack[100]; strcpy(stack,stackk); if(s[i] == '\0' && t != 0 && p[j] != '\0' && stack[t-1]!=p[j]) return; if(t == 0) { if(s[i] == '\0') { for(m = 0;m<k;m++) { printf("%c",path[m]); if(m != k-1) printf(" "); } printf("\n"); return; } stackk[t++] = s[i++]; path[k++] = 'i'; sta(s,p,stackk,i,j,t); k -- ; } else { if(s[i] != '\0') { path[k++] = 'i'; stackk[t++] = s[i++]; sta(s,p,stackk,i,j,t); t--; k--; i--; } if(stack[t-1] == p[j]) { path[k++] = 'o'; sta(s,p,stackk,i,j+1,t-1); k--; } }}int main(){ char s[100],p[100],stack[100]; while(scanf("%s",s)!= EOF) { scanf("%s",p); printf("[\n"); if(strlen(s) == strlen(p)) sta(s,p,stack,0,0,0); printf("]"); } return 0;} #include<stdio.h>#include<string.h>char path[200];int k = 0;int len;//source word 的长度 addedint t;//addedvoid sta(char *s,char *p,char *stackk,int i,int j)//t不要参加递归 void sta(char *s,char *p,char *stackk,int i,int j,int t){ int m = 0; //不需再设此变量 char stack[100]; //strcpy(stack,stackk); //if(s[i] == '\0' && t != 0 && p[j] != '\0' && stack[t-1]!=p[j]) // return; if(j == len)//if(t == 0) { //if(s[i] == '\0') //{ for(m = 0;m<len*2;m++)//for(m = 0;m<k;m++) { printf("%c ",path[m]);//题目要求each i and o is followed by a single space //if(m != k-1) // printf(" "); } printf("\n"); return; //} // stackk[t++] = s[i++]; //path[k++] = 'i'; //sta(s,p,stackk,i,j,t); //k -- ; } else { if(i<len)//if(s[i] != '\0') { path[k++] = 'i'; stackk[t++] = s[i++]; sta(s,p,stackk,i,j); //sta(s,p,stackk,i,j,t); t--; k--; i--; } if(t&&stackk[t-1] == p[j])//if(stack[t-1] == p[j]) { char c;//added path[k++] = 'o'; c = stackk[--t];//added sta(s,p,stackk,i,j+1);//sta(s,p,stackk,i,j+1,t-1); k--; stackk[t++] = c;//added } }}int main(){ char s[100],p[100],stack[100]; while(scanf("%s",s)!= EOF) { scanf("%s",p); printf("[\n"); if((len=strlen(s)) == strlen(p))//if(strlen(s) == strlen(p)) sta(s,p,stack,0,0);//sta(s,p,stack,0,0,0); printf("]\n"); //漏了\n printf("]"); } return 0;}