Question

How to find longest palindrome substring in C

Answer 1

#include <stdio.h>
#include <string.h>
 
int longestPalindromeSubstring(const char* str) {
    int len = strlen(str);
    int longestLength = 1, start = 0;
 
    for (int i = 0; i < len; i++) {
        for (int j = i; j < len; j++) {
            int palindrome = 1;
 
            for (int k = 0; k < (j - i + 1) / 2; k++) {
                if (str[i + k] != str[j - k]) {
                    palindrome = 0;
                }
            }
 
            if (palindrome && (j - i + 1) > longestLength) {
                start = i;
                longestLength = j - i + 1;
            }
        }
    }
 
    printf("Longest palindrome substring = ");
    for (int i = start; i <= start + longestLength - 1; i++)
        printf("%c", str[i]);
    printf("\n");
 
    return longestLength;
}
 
int main()
{
    const char* str = "qabcbaproggorpxyyxzv";
    
    printf("Length palindrome substring length = %d\n", longestPalindromeSubstring(str));
    
    return 0;
}




/*
run:

Longest palindrome substring = proggorp
Length palindrome substring length = 8

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <stdio.h>
#include <string.h>
 
int longestPalindromeSubstring(const char* str) {
    int len = strlen(str);
    int longestLength = 1, start = 0;
 
    for (int i = 0; i < len; i++) {
        for (int j = i; j < len; j++) {
            int palindrome = 1;
 
            for (int k = 0; k < (j - i + 1) / 2; k++) {
                if (str[i + k] != str[j - k]) {
                    palindrome = 0;
                }
            }
 
            if (palindrome && (j - i + 1) > longestLength) {
                start = i;
                longestLength = j - i + 1;
            }
        }
    }
 
    printf("Longest palindrome substring = ");
    fwrite(str + start, 1, longestLength, stdout);
    printf("\n");
 
    return longestLength;
}
 
int main()
{
    const char* str = "qabcbaproggorpxyyxzv";
    
    printf("Length palindrome substring length = %d\n", longestPalindromeSubstring(str));
    
    return 0;
}




/*
run:

Longest palindrome substring = proggorp
Length palindrome substring length = 8

*/

 

70+ SQL courses for beginners and professionals

Answer 3

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

// Expand around center and return length of palindrome
int expandAroundCenter(const char* str, int left, int right) {
    int len = strlen(str);
    while (left >= 0 && right < len && str[left] == str[right]) {
        left--;
        right++;
    }
    return right - left - 1; // actual length
}

int longestPalindromeSubstring(const char* str) {
    int len = strlen(str);
    if (len == 0) return 0;

    int start = 0, end = 0;

    for (int i = 0; i < len; i++) {
        int len1 = expandAroundCenter(str, i, i);     // Odd length
        int len2 = expandAroundCenter(str, i, i + 1); // Even length
        int maxLen = (len1 > len2) ? len1 : len2;

        if (maxLen > end - start) {
            start = i - (maxLen - 1) / 2;
            end = i + maxLen / 2;
        }
    }

    printf("Longest palindrome substring = ");
    for (int i = start; i <= end; i++)
        putchar(str[i]);
    printf("\n");

    return end - start + 1;
}

int main() {
    const char* str = "qabcbaproggorpxyyxzv";
    
    int length = longestPalindromeSubstring(str);
    printf("Length palindrome substring length = %d\n", length);
    
    return 0;
}

 
 
/*
run:
 
Longest palindrome substring = proggorp
Length palindrome substring length = 8
 
*/

 

 

70+ SQL courses for beginners and professionals