Largest Palindrome in C

Question

Really need help!

This code should find a largest palindrome in a string. Which means if there are "abcdcba" and "cdc" in the same string, it should print "abcdcba" out since the length is longer. The function takes a string str and 2 points i and j and determines whether the string from i to j is a palindrome. If it is a palindrome, returns the length of the palindrome and if it is not, returns -1.

int palindromelength(char *str, int i, int j){
        int *first = &i, *last = &j;
        int len;

        while (first < last){
                if (toupper(*first) != toupper(*last))
                        return -1;
                first++;
                last--;
        }
        len = last - first;
        return (len);
}

int main() {
    int length, i, j;
    char str;

    scanf("%s", &str);
    length = strlen(str);

    printf("Length = %d\n", palindromelength(str, i, j));
    //should print out largest palindrome.
    return 0;
}

Answer 1

There is an easy to understand solution to find out longest palindrome in a string.

Key Concept: at the center of a palindrome, characters are always of the form
"....x y x...." or "......x x......"

step1: scan the string from start to end for the xyx or xx patterns and store the center indices in an auxiliary array.

step2: now around each center try to expand the string in both direction and store the lengths.

step3: return the max length.

This approach takes O(N2) order time.

Answer 2

You send your function a string and two indexes, then immediately take the address of two indexes and proceeded to increment/decrement the indexes without any relation or regard to your string. That will never get you anywhere.

While it is fine to try and do all comparisons with indexes as integers, it is probably a bit easier to approach finding palindromes operating on strings and characters instead. You use the indexes to set the start and end position within the string. The indexes by themselves are just numbers. Your first and last should not hold the address to the intergers, they should hold the address of the first and last characters of your search string.

Below is a quick example of using the indexes to locate the start and end characters for your search. Note: I use p (pointer) for first and ep (end pointer) for your last. Look over the logic and let me know if you have questions. The program takes 3 arguments, the string, start and end indexes within the string (0 based indexes):

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

#define MAXP 128

int get_palindrome (char *s, size_t i, size_t j);

int main (int argc, char **argv) {

    if (argc < 4 ) {
        fprintf (stderr, "error: insufficient input, usage: %s str i j\n", argv[0]);
        return 1;
    }

    size_t i = atoi (argv[2]);
    size_t j = atoi (argv[3]);
    char palindrome[MAXP] = {0};

    int len = get_palindrome (argv[1], i, j);

    if (len > 0)
    {
        strncpy (palindrome, argv[1] + i, len);
        printf ("\n palindrome: %s  (%d chars)\n\n", 
                palindrome, len);
    }
    else
        printf ("\n no palindrome for for given indexes.\n\n");

    return 0;
}

int get_palindrome (char *s, size_t i, size_t j)
{
    if (!s || *s == 0) return -1;

    int len = 0;
    char *p = s + i;        /* set start/end pointers   */
    char *ep = s + j + 1;
    char *sp = NULL;
    int c = *ep;            /* save char from string    */

    *ep = 0;                /* null-terminate at end    */
    char *s2 = strdup (p);  /* copy string to s2        */
    *ep = c;                /* replace original char    */

    p = s2;                 /* set s2 start/end ponters */
    ep = s2 + j - i;

    while (ep > p)          /* check for palindrome     */
    {
        if (toupper(*ep) != toupper(*p))
        {
            *ep = 0;
            sp = NULL;
        }
        else if (!sp)
            sp = p;

        p++, ep--;
    }

    len = sp ? (int) strlen (sp) : -1;  /* get length   */

    if (s2) free (s2);      /* free copy of string      */

    return len;             /* return len or -1         */
}

Output

$ ./bin/palindrome 1234abcdcba 4 10

 palindrome: abcdcba  (7 chars)

Note the use of size_t type instead of int for i & j. i & j are indexes and will not be negative for the purpose of this problem. Try to always choose your data type to best fit your data. It will help identify and prevent problems in your code.

Also note, you should make a copy of the string in the function (if you are concerned about preserving the original). Inserting null-terminating characters locating palindromes will alter the original string otherwise.

Answer 3

1. What you describe and what the function is supposed to do are inconsistent: "The function takes a string str and 2 points i and j and determines whether the string from i to j is a palindrome. If it is a palindrome, returns the length of the palindrome and if it is not, returns -1"

Therefore the function should returen either j - i or -1

2. char str; scanf("%s", &str);

This is not how you should declare then initialize a string. Use instead:

char str[512];
scanf ("%s", str);

Also note that you'll need to ask the user to input the length of that string, and you'll need to pass that length as argument in the "palindromelength" function

3. You access the (i+1)th entry of your string like this:

   str[i]

but before, you need to check that i is strictly lower than the length of your string. And don't forget to initialize i and j in your main() function

4. Before starting to code, write an algorithm in pseudocode which can solve your problem and evaluate its complexity. In this case, the comlpexity of the most obvious algorithm would be O(n^2), where n is the length of the string. This most obvious solution would be to check every substring, but maybe there are better algorithms: en.wikipedia.org/wiki/Longest_palindromic_substring