杭电oj 1515题,该如何解决

杭电oj 1515题
题目链接：//http://acm.hdu.edu.cn/showproblem.php?pid=1515

C/C++ code


#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;
}

测试样例都正确，但是ac不了。
用的搜索做的。
各位大神帮忙看一下，是不是有哪个细节没有注意到。谢谢！

------解决方案--------------------
以下可能改多了，但这样才能AC.

C/C++ code

#include<stdio.h>
#include<string.h>

char path[200];
int k = 0;
int len;//source word 的长度  added
int t;//added

void 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;
}

杭电oj 1515题,该如何解决

相关推荐