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

This is a discussion on See I have 2 string, i need to check whether 2nd sting is jumbled form of first sting within the C Programming forums, part of the General Programming Boards category; Output is coming equal; how come? If string 1 is "dabcd" and string 2 is "bcadd" then it should show ...

  1. #1
    Registered User
    Join Date
    Sep 2012
    Posts
    8

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

    Output is coming equal; how come?

    If string 1 is "dabcd" and string 2 is "bcadd" then it should show similar strings.
    Any one can suggest any other easy way to do this....

    Code:
    #include<stdio.h>
     
    int main()
    {
        char a[]="abcd";
        char b[]="zdab";
        char temp = '0';
        int i=0,j=0;
        int n=sizeof(a);  
        for(i=0;i<n-1;i++)
        {   
          for(j=0;j<n-i-1;j++)
          {   
             if(a[j]>a[j+1])
             {   
                temp =a[j];
                a[j] = a[j+1];
                a[j+1]=temp;
             }   
              if(b[j]>b[j+1])
             {   
                temp =b[j];
                b[j] = b[j+1];
                b[j+1]=temp;
             }   
           }   
        }   
         
        for(i=0;i<n;i++)
        {   
           printf("%c %c\n",a[i],b[i]);
        }   
       if(strcmp(a,b)==0)
           printf("similar and jumbled");
       else
           printf("unequal");    
        return 0;
    }
     
    output :
     
    a a
    b b
    c d
    d z
    similar and jumbled

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,333
    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"
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    383
    What is the output when you change this line:
    Code:
           printf("%c %c\n",a[i],b[i]);
    to this?
    Code:
           printf("%d %d\n",a[i],b[i]);
    Hint: your sorting loop needs to be fixed.

  4. #4
    Registered User
    Join Date
    Sep 2012
    Posts
    8

    Question suggest easier way plzzz

    Quote Originally Posted by christop View Post
    What is the output when you change this line:
    Code:
           printf("%c %c\n",a[i],b[i]);
    to this?
    Code:
           printf("%d %d\n",a[i],b[i]);
    Hint: your sorting loop needs to be fixed.

    Yup...
    if i use n = sizeof(a)-1;

    then its working....


    Any 1 plz suggest easier way to do this.

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,333
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Use "counting sort" to record the letters into another array. csorta[128] would have csorta[ascii value of a letter]++ (incremented). So 'a' would give csorta['a']++.

    if b[] had an 'a' in it, then it would also have csortb['a']++. Adding 1 to csortb['a'] for every 'a' in the b string of chars.

    Then just check csorta to csortb

    Pseudo of code:
    Code:
    for(i='A',notEqual=0;i<='z'; i++) {
       if(csorta[i] != csortb[i]) {
         notEqual = 1;
         break;
       }
    }
    if(notEqual)
       printf("Strings are not equal\n");
    else
       printf("Strings have the same letters in them\n");
    You can download an ascii table from several places on the net, just google it. Any programming book, and lots of compilers have them, as well. You can also make your own compiler show them, pretty easily (not as convenient though unless you print it out).

    The advantage is shorter code, and no sorting. No char's are moved in the running of this program!

  7. #7
    Registered User
    Join Date
    Sep 2012
    Posts
    8
    Thanx for reply,

    @ Salem : I understood, means I am first sorting n elements and then comparing n elements.
    But according to your logic i need to delete common k element and compare remaining only n-k elements.

  8. #8
    Registered User
    Join Date
    Sep 2012
    Posts
    8
    Thanks for reply.

    @ Adak : 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.
    here also first we are sorting n element into an array then comparing until we find mismatch, so more comparison happening.

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by ypp174 View Post
    Thanks for reply.

    @ Adak : 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.
    here also first we are sorting n element into an array then comparing until we find mismatch, so more comparison happening.
    That's a very thoughtful reply. I'm impressed by it.

    Take a run at this, however, and tell me what you think.

    Code:
    #include <stdio.h>
    #include <string.h>
    
    int encrypt (int num);
    
    int main(void) {
       char a[50]={"Once a jolly swagman"};
       char b[50]={"cegajlnwolsanOyam"};
       char counta[127], countb[127];
       int i, lena, lenb, maxlen, notEqual;
    
       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");
       else
          printf("Strings contain the same letters\n");
    
       return 0;
    }

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,954
    Quote 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!"

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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;
    }
    Last edited by Adak; 09-23-2012 at 07:03 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sting and Char Funny Problem
    By ncode in forum C Programming
    Replies: 3
    Last Post: 11-23-2011, 04:36 PM
  2. Help - Function returning a sting
    By AmiTsur in forum C Programming
    Replies: 1
    Last Post: 11-08-2002, 06:47 AM
  3. converting int to sting
    By LWisne in forum C++ Programming
    Replies: 7
    Last Post: 10-14-2002, 08:07 AM
  4. ctime and sting copy
    By Sue Paterniti in forum C Programming
    Replies: 9
    Last Post: 04-21-2002, 10:04 PM
  5. Sting Manipulation!!Pls Help
    By vij30 in forum C Programming
    Replies: 3
    Last Post: 03-15-2002, 12:43 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21