Thread: See I have 2 string, i need to check whether 2nd sting is jumbled form of first sting

Somehow, your "sort" function managed to move the \0 to the start of the string.

Code:

Breakpoint 1, main () at foo.c:33
33	   if(strcmp(a,b)==0)
(gdb) print a
$1 = "\000abcd"
(gdb) print b
$2 = "\000abdz"

Well how are you measuring "similar"?

At the moment, you're comparing "abcd" with "abdz". The comparison stops being equal at 50% of the string length.

But rearranged as "abdc" and "abdz", the comparison stops being equal at 75% of the string length.

Perhaps a different approach would be to take
char a[]="abcd";
char b[]="zdab";

and eliminate from both arrays any letter which is common to both.

So for example, on the first pass, you see both have an 'a', so both become
a[]="bcd";
b[]="zdb";

Eventually, you end up with
a[]="c";
b[]="z";
where each array contains only letters not in the other string.

Obviously, if the strings were identical, or just a permutation, both resultant strings would be empty.

How you decide how two non-empty strings are on a scale from "very similar" to "different" is another matter.

Originally Posted by ypp174

I thought of this solution but user input any character even spacial character.
So if input string length is more than available total ascii values(255) then it is ok
but what if input string length is small like 10 to 20 letter then it would be not efficient i guess.

You still are going to assume that each character fits into a char, so this means 256 different values, assuming that CHAR_BIT is 8. Therefore, counting sort is applicable.

As for efficiency: if the input string length is small and limited to only a few values, then indeed Adak's idea for using counting sort would not be efficient. On the other hand, efficiency does not matter when the size of the input is so small. On a modern computer, I expect that even bogosort would be fast enough to sort a 20 character array before you can say "the array is sorted!"

Originally Posted by ypp174

here also first we are sorting n element into an array then comparing until we find mismatch, so more comparison happening.

With an efficient sort, you will likely use fewer comparisons than without sorting, assuming that the size of the input is large enough.

Yep, it's OK for efficiency.

Code:

/*
 Words are from the Roberta Flack version of the song, 1969, from here:

http://www.youtube.com/watch?v=hOFrGbuUqnQ

Great listen! ;)
*/

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

int encrypt (int num);

int main(void) {
   char a[]={
      "The first time, ever I saw your face.\n"
      "I thought the sun, rose in your eyes.\n"
      "And the moon and the stars, were the gifts you gave,\n" 
      "to the dark, and the endless skies, my love.\n"
      "To the dark, and the endless skies.\n\n"

      "And the first time, ever I kissed your mouth.\n"
      "I felt the earth, move in my hand.\n"
      "Like the trembling heart, of a captive bird,\n"
      "that was there, at my command, my love.\n"
      "That was there, at my command, my love.\n\n"

      "And the first time, ever I lay with you,\n"
      "I felt your heart, so close to mine.\n"
      "And I knew our joy, would fill the earth,\n"
      "and last, till the end of time, my love.\n"
      "And it would last, till the end of time, my love.\n\n"
      "The first time, ever I saw, your face.\n"
      "Your face. Your face. Your face.\n"
   };

   char b[]={
      "The first time, ever I saw your face.\n"
      "I thought the sun, rose in your eyes.\n"
      "And the moon and the stars, were the gifts you gave,\n" 
      "to the dark, and the endless skies, my love.\n"
      "To the dark, and the endless skies.\n\n"

      "And the first time, ever I kissed your mouth.\n"
      "I felt the earth, move in my hand.\n"
      "Likes the trembling heart, of a captive bird,\n"      //appended an s to Like, 
      "that was there, at my command, my love.\n"
      "That was there, at my command, my love.\n\n"

      "And the first time, ever I lay with you,\n"
      "I felt your heart, so close to mine.\n"
      "And I knew our joy, would fill the earth,\n"
      "and last, till the end of time, my love.\n"
      "And it would last, till the end of time, my love.\n\n"
      "The first time, ever I saw, your face.\n"
      "Your face. Your face. Your face.\n"
   };
      
   char counta[127], countb[127];
   int i, lena, lenb, maxlen, notEqual;
   clock_t start,stop;
   start=clock();


   for(i=0;i<127;i++) {
      counta[i]=0;
      countb[i]=0;
   }
   
   lena=strlen(a);                    //get their respective lengths
   lenb = strlen(b);
   if(lena > lenb)
      maxlen = lena;
   else
      maxlen = lenb;

      
   for(i=0;i<=maxlen;i++) {            //and catalogue the values
      if(i<lena)
         counta[a[i]]++;
   
      if(i<lenb)
         countb[b[i]]++;
   }
   for(i='A',notEqual=0;i<='z';i++) { //now compare them
      if(counta[i] != countb[i]) {
         notEqual = 1;
         printf("Not equal: %c   counta[i]: %d  countb[i]: %d\n",i,counta[i], countb[i]); //getchar();
         break;
      }
      //printf("i: %c Is equal: counta[i]: %d  countb[i]: %d\n",i,counta[i], countb[i]); getchar();
   }
   if(notEqual)
      printf("Strings contain different letters\n\n");
   else
      printf("Strings contain the same letters\n");

   stop = clock();
   printf("Elapsed time: %f seconds\n",(double)(stop-start)/CLOCKS_PER_SEC);


   printf("Display the strings [y/any] ? ");
   i=getchar();
   if(i=='y')
      printf("a:\n%s\n\n b:\n%s\n",a,b);


   return 0;
}