To solve this problem, we need to find the longest palindromic substring in a given string. A palindrome is a string that reads the same forwards and backwards. The approach involves expanding around potential centers of palindromes (each character for odd-length palindromes and each pair of consecutive characters for even-length palindromes) to find the longest valid palindrome.

Approach

1. Edge Cases: If the input string is empty or has only one character, return the string itself as it is a palindrome.
2. Expand Around Centers: For each character in the string:
   • Expand around the character as the center (for odd-length palindromes).
   • Expand around the character and the next character as the center (for even-length palindromes).
3. Track Maximum Length: Keep track of the longest palindrome found by updating the start and end indices whenever a longer palindrome is discovered.
4. Extract Result: Using the start and end indices of the longest palindrome, extract and return the substring.

Solution Code

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

int expandAroundCenter(char *s, int left, int right) {
    while (left >= 0 && right < strlen(s) && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}

char* longestPalindrome(char* s) {
    if (s == NULL || strlen(s) < 1) return "";
    int start = 0, end = 0;
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int max_len = len1 > len2 ? len1 : len2;
        if (max_len > end - start) {
            start = i - (max_len - 1) / 2;
            end = i + max_len / 2;
        }
    }
    int result_len = end - start + 1;
    char *result = (char*)malloc(result_len + 1);
    strncpy(result, s + start, result_len);
    result[result_len] = '\0';
    return result;
}

int main() {
    char input[1000];
    scanf("%s", input);
    char *output = longestPalindrome(input);
    printf("%s\n", output);
    free(output);
    return 0;
}

Explanation

• Expand Around Center: The expandAroundCenter function takes the string and two indices (left and right) and expands outwards as long as the characters at these indices are equal. It returns the length of the palindrome found.
• Longest Palindrome Calculation: The longestPalindrome function iterates over each character, checks both odd and even length palindromes, and updates the start and end indices of the longest palindrome.
• Result Extraction: The result is extracted using the start and end indices, allocated dynamically, and returned. The main function reads input, calls the longestPalindrome function, prints the result, and frees the allocated memory.

This approach efficiently finds the longest palindromic substring with a time complexity of O(n²) and space complexity of O(1) (excluding the result storage). It is optimal for this problem given the constraints.

作者声明:本文包含人工智能生成内容。