Thread: the palindrome

  1. #1
    Registered User
    Join Date
    Oct 2008
    Location
    china
    Posts
    16

    the palindrome

    /*
    this program from a master's blog but i don't know what dose it work,hope
    that somebody will explain this working detailedly(may be related to the
    palindrome ).

    this's about descriptions to be solved quesion:

    Catcher to be an agent of MCA country,he have been found any symmetrical code
    that enemy states used to comunicate with,such as:
    ABBA,ABA,A,123321 .


    but they sometimes encoded into irrelevant characters to prevent others contry
    's crack,such as the following Variants:
    ABBA->12ABBA,ABA->ABAKK,123321->51233214

    because of being intercepted characters to be too long,and with vary situation(abaab
    seems to be aba ,or baaab),of catcher ' s a great deal of working ,he have
    to get master helping,could you find out the lengthest vaild characters?


    */
    Code:
    #include <stdio.h> 
    #include <string.h> 
    #include <memory.h> 
    //#include <assert.h> 
    #define MAX_LEN 80 
    char szInput[MAX_LEN+1]; 
    unsigned char B[(MAX_LEN+1)*MAX_LEN/8];
    unsigned char Bit8={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
    #define GETB(i,j) (B[(i)*10+((j)>>3)] & Bit8[(j) & 0x7]) 
    #define SETB(i,j) (B[(i)*10+((j)>>3)] |= Bit8[(j) & 0x7]) 
    int length; 
    int getcode() 
    { 
    int i,j,notfound1,notfound2=0; 
    if(length <2) 
    return 1; 
    memset(B,0,(length+1)*10);//MAX_LEN/8? 
    for(i=0;i <2;++i) 
    { 
    for(j=0;j <length;++j) 
    SETB(i,j);//B[j]=1; 
    } 
    for(i=2;i <=length;++i) 
    { 
    for(notfound1=1,j=0;j <=length-i;++j) 
    { 
    if(GETB(i-2,j+1)/*B[i-2][j+1]*/ && szInput[j]==szInput[j+i-1]) 
    { 
    SETB(i,j);//B[j]=1; 
    //printf("%d,%d = 1\n",i,j); 
    notfound1=0; 
    } 
    } 
    if(notfound1) 
    { 
    if(notfound2) 
    return i-2; 
    notfound2=1; 
    } 
    else 
    { 
    notfound2=0; 
    } 
    } 
    if(notfound2) 
    return length-1; 
    return length; 
    } 
    
    int main(void) 
    { 
    
    while(scanf("%s",szInput)!=EOF) 
    { 
    length=strlen(szInput); 
    //assert(length <=MAX_LEN); 
    printf("%d\n",getcode()); 
    } 
    return 0; 
    }
    Last edited by haochao; 10-11-2008 at 07:20 AM.

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    china
    Posts
    16
    晕,看来我还是回国内论坛吧.
    自己还得语言方面努力.............

  3. #3
    Registered User
    Join Date
    Oct 2008
    Location
    china
    Posts
    16
    maybe i describe something wrong????????????????????????????????????????????? ???????????
    tell me!

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    There is a logical (syntax) error here (should be quite obvious):

    Code:
    unsigned char Bit8={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
    Of course, if you didn't write this code and you can't understand it (neither can I), how's it going to help you?

  5. #5
    Registered User
    Join Date
    Oct 2008
    Location
    china
    Posts
    16
    sorry.the code:
    Code:
    unsigned char Bit8[]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
    what's an algorithm used?

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    The first thing to do is to indent the code so that you can read it . . .
    Code:
    #include <stdio.h>
    #include <string.h>
    #include <memory.h>
    //#include <assert.h>
    #define MAX_LEN 80
    char szInput[MAX_LEN+1];
    unsigned char B[(MAX_LEN+1)*MAX_LEN/8];
    unsigned char Bit8[]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
    #define GETB(i,j) (B[(i)*10+((j)>>3)] & Bit8[(j) & 0x7])
    #define SETB(i,j) (B[(i)*10+((j)>>3)] |= Bit8[(j) & 0x7])
    int length;
    int getcode()
    {
        int i,j,notfound1,notfound2=0;
        if(length <2)
            return 1;
        memset(B,0,(length+1)*10);   //MAX_LEN/8?
        for(i=0;i <2;++i)
        {
            for(j=0;j <length;++j)
                SETB(i,j);           //B[j]=1;
        }
        for(i=2;i <=length;++i)
        {
            for(notfound1=1,j=0;j <=length-i;++j)
            {
                if(GETB(i-2,j+1)/*B[i-2][j+1]*/ && szInput[j]==szInput[j+i-1])
                {
                    SETB(i,j);       //B[j]=1;
                    //printf("&#37;d,%d = 1\n",i,j);
                    notfound1=0;
                }
            }
            if(notfound1)
            {
                if(notfound2)
                    return i-2;
                notfound2=1;
            }
            else
            {
                notfound2=0;
            }
        }
        if(notfound2)
            return length-1;
        return length;
    }
    
    
    int main(void)
    {
    
        while(scanf("%s",szInput)!=EOF)
        {
            length=strlen(szInput);
            //assert(length <=MAX_LEN);
            printf("%d\n",getcode());
        }
        return 0;
    }
    Of course, "legible" is a relative term.

    I can't make much sense of that code, but I'd guess that the outer for loop steps through each character in the string, and the inner for loop determines how long of a palindrome is present at that point.

    FWIW, here's my version:
    Code:
    #include <stdio.h>
    #include <stddef.h>
    #include <string.h>
    
    int longest_palindrome(const char *string);
    
    int main() {
        char string[BUFSIZ], *p;
        int length;
        
        while(fgets(string, sizeof string, stdin)) {
            /* remove the newline, if any, from the string */
            if((p = strchr(string, '\n'))) *p = 0;
            
            length = longest_palindrome(string);
            printf("longest palindrome: %d\n", length);
        }
        
        return 0;
    }
    
    int longest_palindrome(const char *string) {
        int length = (int)strlen(string), pal_length;
        int start, end, offset;
        int longest = 0;
        int still_palindrome = 0;
        
        if(!length) return 0;
        
        for(start = 0; start < length; start ++) {
            for(end = length - 1; end >= start; end --) {
                pal_length = end - start + 1;
                
                /* check if the string between string[start] and string[end] is a
                    palindrome. */
                
                still_palindrome = 1;
                for(offset = 0; still_palindrome && offset <= pal_length / 2;
                    offset ++) {
                    
                    if(string[start + offset] != string[end - offset]) {
                        still_palindrome = 0;
                    }
                }
                
                if(still_palindrome) {
                    printf("    found: \"%.*s\"\n", pal_length, string + start);
                    if(pal_length > longest) {
                        printf("        (set as longest)\n");
                        longest = pal_length;
                    }
                }
            }
        }
        
        return longest;
    }
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Registered User
    Join Date
    Oct 2008
    Location
    china
    Posts
    16
    thanks,thamks...
    it's seem to me that i will learn indention of the code,how can i get the code indention quickly?

  8. #8
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Well, it's best to keep your code indented as you're writing it. If you find someone else's code that is a mess like that, though, you can automatically indent it with some program or another. At the moment, I like bcpp for that.

    cpwiki.sf.net/Indentation

    [edit] Oh, and the syntax highlighting is from codeform. http://dwks.theprogrammingsite.com/myprogs/cfonline.htm [/edit]

    Out of curiosity, what are you trying to do? I'm guessing that you were searching for information about palindromes and found that?
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  9. #9
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Hmmm this thread was closed... Interesting. Anyway, it looks to me (thanks to the clean-up job done by dwks) that it compares blocks of data at a time. I often write code like this too, but at least I comment the hell out of it for my peers' sanity sake.

  10. #10
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    My amazing clean-up job was the product of one command: something like "bcpp file.c > file-indented.c".

    So, yeah. If you're looking for simple palindrome stuff, I suggest you find some other code. If you're looking to understand how that code works, hopefully my code showed you another way to do it. In that case, I still suggest you find some other code.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  11. #11
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    To be honest, I don't see some sort of huge performance gain in the "master" code presented to us in the beginning. It was loftily difficult to follow without scrolling back and forth a couple of times.

    If you are trying to learn programming by writing something to do palindromes, why are you even looking for samples? Just do what you think will work. And so what if it ends up being 275 lines.

  12. #12
    Registered User
    Join Date
    Oct 2008
    Location
    china
    Posts
    16
    Out of curiosity, what are you trying to do? I'm guessing that you were searching for information about palindromes and found that?
    i'm researching algorithm,i can 't figure out the code .
    Code:
    unsigned char Bit8[]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
    #define GETB(i,j) (B[(i)*10+((j)>>3)] & Bit8[(j) & 0x7])
    #define SETB(i,j) (B[(i)*10+((j)>>3)] |= Bit8[(j) & 0x7])

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by haochao View Post
    i'm researching algorithm,i can 't figure out the code .
    Yeah, it looks like it was written that way on purpose. Anyway, what you quoted is remarkably straightforward, considering:
    Code:
    unsigned char Bit8[]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
    #define GETB(i,j) (B[(i)*10+((j)>>3)] & Bit8[(j) & 0x7])
    #define SETB(i,j) (B[(i)*10+((j)>>3)] |= Bit8[(j) & 0x7])
    These are pseudo-functions. Once you remember that >>3 is the same as /8, and that & 0x7 is the same as "remainder when divided by 8", that allows you to rewrite GETB as something like
    Code:
    B[10*i + j/8] & Bit8[j%8];
    and SETB would be
    Code:
    B[10*i+j/8] |= Bit8[j%8];
    And also Bit8[i] is all zeroes, except for one bit turned on in the i'th position (counting with 0 as the most significant bit). & checks whether that particular bit is "on", while |= makes sure that particular bit is "on".

  14. #14
    Registered User
    Join Date
    Oct 2008
    Location
    china
    Posts
    16
    that's made a startling.
    thanks
    counting with 0 as the most significant bit
    what you're meaning?

    and what purpose it was written that way
    Code:
    char szInput[MAX_LEN+1];
    unsigned char B[(MAX_LEN+1)*MAX_LEN/8];
    Last edited by haochao; 10-11-2008 at 10:31 PM.

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    The most significant bit is the one that's worth the most (in this case, the one that's worth 128, as opposed to the one that's worth 1).

    And those other are just char arrays.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Error in Recursive String Palindrome Code
    By clegs in forum C Programming
    Replies: 13
    Last Post: 12-21-2008, 12:36 PM
  2. Is it a Palindrome?
    By xp5 in forum C Programming
    Replies: 3
    Last Post: 09-06-2007, 05:26 AM
  3. bool palindrome definition
    By justinc911 in forum C++ Programming
    Replies: 3
    Last Post: 11-26-2003, 05:50 PM
  4. Palindrome Coding trouble
    By TheLoneWolf32 in forum C++ Programming
    Replies: 3
    Last Post: 02-22-2003, 07:05 PM
  5. palindrome HELP !!!
    By TED22_8 in forum C Programming
    Replies: 23
    Last Post: 01-22-2002, 02:14 PM