Program 1:

[Gauthkum]

Solve the below problem:

Write a C program that reads in a string as input from us and to print the longest palindrome that can be formed from the characters in the string.

Note:

A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward (ignoring spaces, punctuation, and capitalization). If there are multiple palindromes of the same length, your program should print out the one that comes first alphabetically. For example, if you enter the string "I have reached final level in racecar game". your program should output "racecar".

[Srudurai]

include

include

include

static inline int min(int x, int y) { return x < y ? x : y; } static int find_longest_substring(char *s, char output[]) { int i, j; char s2[3000] = { '\0' };

s2[0] = '$';
for (i = 0; s[i] != '\0'; i++) {
    s2[(i<<1)+1] = '#';
    s2[(i<<1)+2] = s[i];
}
s2[(i<<1)+1] = '#';
int len = (i<<1)+2;
s2[len] = '\0';

int p[3000] = { 0 }; 
int id = 0;  
int limit = 0;  
int max_len = 0;  
int max_id = 0;  
for (i = 1; i < len; i++) {
    if (i < limit) {
        p[i] = min(p[2*id-i], limit-i);
    } else {
        p[i] = 1;
    }

    while (s2[i+p[i]] == s2[i-p[i]]) {
        p[i]++;
    }

    if (i+p[i] > limit) {
        limit = i+p[i];
        id = i;
    }
    if (max_len < p[i]-1) {
        max_len = p[i]-1;
        max_id = i;
    }
}

for (j = 0, i = max_id - max_len; i <= max_id+max_len; i++) {
    if (s2[i] != '#') {
        output[j++] = s2[i];
    }
}
return max_len;

}

static char longest_Palindrom(char s) { int i; if (s == NULL) { return NULL; }

int len = strlen(s);
if (len <= 1) {
    return s;
}

char *palindrome_str = malloc(2000);
memset(palindrome_str, 0, sizeof(palindrome_str));

int size = find_longest_substring(s, palindrome_str);
palindrome_str[size] = '\0';
return palindrome_str;

}

int main(void) { char *str1 = "I have reached final level in racecar game"; printf("\nOriginal String: %s", str1); printf("\nLongest palindromic substring of the said string: %s\n", longest_Palindrom(str1)); return 0; }

Output: Original String: I have reached final level in racecar game Longest palindromic substring of the said string: racecar