Finding the Longest Palindromic Substring in C

Program Structure

This C program finds the longest palindromic substring in a given string using a dynamic programming approach.
It utilizes a 2D array to store boolean values indicating whether substrings are palindromic. The program then iterates through
the array to determine the longest palindromic substring.

Program Explanation

1. Include Headers: The program includes necessary headers for standard input-output functions.
2. Function Definitions:
   • printLongestPalindromicSubstring(char str[]): Finds and prints the longest palindromic substring.
   • main(): Entry point of the program where the string is initialized and the function is called.

Program Code

#include 
#include 
#include 

// Function to print the longest palindromic substring
void printLongestPalindromicSubstring(char str[]) {
    int n = strlen(str);
    bool table[n][n];
    int start = 0;
    int maxLength = 1;

    // Initialize the table
    memset(table, false, sizeof(table));

    // All substrings of length 1 are palindromes
    for (int i = 0; i < n; i++) {
        table[i][i] = true;
    }

    // Check substrings of length 2
    for (int i = 0; i < n - 1; i++) {
        if (str[i] == str[i + 1]) {
            table[i][i + 1] = true;
            start = i;
            maxLength = 2;
        }
    }

    // Check substrings of length greater than 2
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            if (table[i + 1][j - 1] && str[i] == str[j]) {
                table[i][j] = true;
                start = i;
                maxLength = len;
            }
        }
    }

    // Print the longest palindromic substring
    printf("Longest palindromic substring is: ");
    for (int i = start; i < start + maxLength; i++) {
        printf("%c", str[i]);
    }
    printf("\\n");
}

int main() {
    char str[] = "babad";
    printLongestPalindromicSubstring(str);
    return 0;
}
    

Program Documentation

• Header Files:
  • #include <stdio.h> – Provides standard input and output functions.
  • #include <string.h> – Provides string manipulation functions.
  • #include <stdbool.h> – Provides boolean data types and constants.
• Function printLongestPalindromicSubstring(char str[]):
  • Initializes a 2D boolean array to track palindromic substrings.
  • Checks all substrings of increasing lengths for being palindromic.
  • Updates the start position and maximum length of the longest palindrome found.
  • Prints the longest palindromic substring.
• Function main():
  • Initializes the string.
  • Calls the function to find and print the longest palindromic substring.

Explanation

1. Header Files:
   • stdio.h for standard I/O functions.
   • string.h for string manipulation.
   • stdbool.h for boolean data types.
2. Function Definitions:
   • printLongestPalindromicSubstring(char str[]): This function calculates and prints the longest palindromic substring using dynamic programming.
   • main(): Initializes the string and calls the function to display the result.
3. Dynamic Programming Approach:
   • A 2D boolean array table is used to keep track of palindromic substrings.
   • Single characters and pairs of characters are initially set as palindromic.
   • Longer substrings are checked by expanding around known palindromic substrings.