最长回文子串C语言怎么写

最长回文子串问题可以使用中心扩展算法或者Manacher算法来解决。

中心扩展算法的思路是从每个字符作为回文中心向两边扩展，记录下最长的回文子串。具体实现如下：

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

#define MAX_LEN 100

void longestPalindrome(char s[]) {
    int left, right, len, maxLen = 1, start = 0;
    int n = strlen(s);
    
    for (int i = 0; i < n; i++) {
        // 以i为中心向两边扩展
        len = 1;
        left = i - 1;
        right = i + 1;
        while (left >= 0 && s[left] == s[i]) {
            left--;
            len++;
        }
        while (right < n && s[right] == s[i]) {
            right++;
            len++;
        }
        while (left >= 0 && right < n && s[left] == s[right]) {
            left--;
            right++;
            len += 2;
        }
        if (len > maxLen) {
            maxLen = len;
            start = left + 1;
        }
    }
    printf("The longest palindrome substring is: ");
    for (int i = start; i < start + maxLen; i++) {
        printf("%c", s[i]);
    }
}

int main() {
    char s[MAX_LEN];
    printf("Enter a string: ");
    scanf("%s", s);
    longestPalindrome(s);
    return 0;
}

Manacher算法是一种优化的算法，其时间复杂度为O(n)，更快速地求解最长回文子串。具体实现如下：

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

#define MAX_LEN 100

void longestPalindrome(char s[]) {
    int n = strlen(s);
    char t[MAX_LEN * 2 + 1];
    int p[MAX_LEN * 2 + 1];
    int center = 0, maxRight = 0, maxLen = 1, start = 0;
    
    // 构造新字符串t
    for (int i = 0; i < n; i++) {
        t[2 * i] = '#';
        t[2 * i + 1] = s[i];
    }
    t[2 * n] = '#';
    int len = 2 * n + 1;
    
    // 求解p数组
    for (int i = 0; i < len; i++) {
        if (i < maxRight) {
            p[i] = p[2 * center - i] < maxRight - i ? p[2 * center - i] : maxRight - i;
        } else {
            p[i] = 1;
        }
        while (i - p[i] >= 0 && i + p[i] < len && t[i - p[i]] == t[i + p[i]]) {
            p[i]++;
        }
        if (i + p[i] > maxRight) {
            maxRight = i + p[i];
            center = i;
        }
        if (p[i] > maxLen) {
            maxLen = p[i];
            start = (i - maxLen + 1) / 2;
        }
    }
    printf("The longest palindrome substring is: ");
    for (int i = start; i < start + maxLen - 1; i++) {
        printf("%c", s[i]);
    }
}

int main() {
    char s[MAX_LEN];
    printf("Enter a string: ");
    scanf("%s", s);
    longestPalindrome(s);
    return 0;
}