Question

C programming question...

Description Johnny is a three years old kids. He likes to eat sugar. Oneday, he sneak into the kitchen in order to grab some sugar to eat. Unfortunately, his papa catch him. His papa call him:" Johnny, Johnny! Johnny reply: "Yes, papa." papa then ask: " Eating sugar?" Johnny lied: " No, papa." At that moment, Johnny begain to think that what's defintion of string equivalent? In this three years old kids' recognition, string a and string b is equivalent if a and b are the same or string a and string b can be devide into two same size part: a1, a2, b1, b2 and the following rules fulfill. For example: a papa " bapap ", we need to check if " pa" equals " ap "in Johnny' rule, therefore we divide" pa " into "p" and "a". Divide " ap" into "a" and "p" Then because "p"--"p" && " a "--"a" we know that "pa"--"ap". therefore we can conclude that " papa " equals " apap" Note that we can't divide a string if the length of the string is an odd number. Help Johnny find out if the two string are the same. If you help him, he will give you some sugar. Input input contains two lines. First line is the string a Second line is the string b the length of the two string are the same and the length is from 1-105 ( 1

Answer 1

this problem can be divided into sub task and then solved easily:

Subtasks:

1:check if both string are equal or not, this task is mandatory for all type of inputs,hence it will be done at starting of function.

2:for odd length string: if strings not equal return 0 i.e. false , otherwise return 1, i.e. true.

3: for even length string : divide each string into 2 substring of equal length ,i.e string 1 will be divided into a1,a2 and b will be divided into b1,b2

Now, check/compare strings a1,b1 and a2,b2

or compare a1,b2 and a2,b1

if any of these two comparison give result true ,then result is true.

This algorithm is implemented by using recursive function as follows:

Below is the C code for the problem:

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

int comparable(char *a, char* b,int size)
{
   int i,flag=0;
   char a1[size/2],b1[size/2],a2[size/2],b2[size/2];
   if(size<1) // String Is Empty
   {
       return 0;      
   }
   for(i=0;i<size;++i) //comparing both string(can be done by strcmp() function also)
   {
       if(a[i]!=b[i]){  
           flag=1;
           break;
       }
   }
  

   if(flag==0)
   {  
       return 1;
   }

   if((size)%2!=0) //if string is of odd length then we only need to compare
            // both strings only once, hence strings will not be comparable
   {  
       return 0;
   }
    //loops to break string a and b into 4 parts: a1,b1,a2,b2
   for(int i=0;i<size/2;++i){
       a1[i]=a[i];
       b1[i]=b[i];
   }
   //assigning null terminator to each string manually
   a1[size/2]='\0';
   b1[size/2]='\0';
   for(int i=0;i<size/2;++i){
       a2[i]=a[i+size/2];
       b2[i]=b[i+size/2];
   }
   //assigning null terminator to each string manually
   a2[size/2]='\0';
   b2[size/2]='\0';
   //compare between (a1,b1) and (a2,b2) or between (a1b2) and (a2b1)
   return ((comparable(a1,b1,size/2)&&comparable(a2,b2,size/2))||(comparable(a1,b2,size/2)&&comparable(a2,b1,size/2)));
}

//driver function
int main()  
{
   int n;
   char a[n],b[n];
   scanf("%s%s",a,b);
   n=strlen(a);
   if(comparable(a,b,n))
   {
       printf("true:Strings are comparable\n");  
   }
   else
       printf("false:Strings are not comparable\n");  
   return 0;
}