C语言算法-解答最长回文子串算法问题的C语言实现

题目

给定一个字符串，找到其中最长的回文子串。

引言

回文串是一个正读和反读都相同的字符串。最长回文子串是给定字符串中最长的回文子串。例如，在字符串 "babad" 中，最长回文子串为 "bab"，而在字符串 "cbbd" 中，最长回文子串为 "bb"。解决这个问题需要使用中心扩展算法。

算法思路

我们将使用中心扩展算法来解决最长回文子串问题。算法的思想是遍历字符串中的每个字符，并以该字符为中心，向两边扩展，以找到以该字符为中心的最长回文子串。我们还需要考虑回文串长度为奇数和偶数两种情况。

算法的步骤如下：

1. 定义一个函数 expandFromCenter，该函数以给定字符串和中心索引为参数，并返回以该中心索引为中心的最长回文子串长度。
2. 定义一个函数 longestPalindrome，该函数将给定字符串作为参数，并返回最长回文子串。
3. 在 longestPalindrome 函数中，遍历字符串中的每个字符。
4. 对于每个字符，调用 expandFromCenter 函数，分别处理回文串长度为奇数和偶数的情况。
5. 比较得到的回文子串长度，更新最长回文子串的起始和结束索引。
6. 根据最长回文子串的起始和结束索引，提取子串并返回。

代码实现

下面是使用C语言实现的代码：

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

int expandFromCenter(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;
    for (int i = 0; i < strlen(s); i++) {
        int len1 = expandFromCenter(s, i, i);      // 处理回文串长度为奇数的情况
        int len2 = expandFromCenter(s, i, i + 1);  // 处理回文串长度为偶数的情况
        int len = len1 > len2 ? len1 : len2;
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }

    char *result = malloc(sizeof(char) * (end - start + 2));
    strncpy(result, s + start, end - start + 1);
    result[end - start + 1] = '\0';

    return result;
}

int main() {
    char input[] = "babad";
    char *result = longestPalindrome(input);
    printf("Input: %s\n", input);
    printf("Longest Palindrome: %s\n", result);

    free(result);

    return 0;
}

算法分析

该算法的时间复杂度为 O(n^2)，其中 n 是字符串的长度。这是因为我们需要遍历字符串中的每个字符，并以每个字符为中心进行扩展。

空间复杂度为 O(1)，除了存储结果之外，我们没有使用额外的空间。

示例和测试

示例输入1:

"babad"

示例输出1:

Longest Palindrome: "bab"

示例输入2:

"cbbd"

示例输出2:

Longest Palindrome: "bb"

总结

本文使用C语言实现了解答最长回文子串算法问题的代码。通过中心扩展算法，我们能够有效地找到给定字符串中的最长回文子串。这个问题是字符串处理中的一个经典问题，解决它需要注意回文串长度为奇数和偶数的情况。该算法的时间复杂度为 O(n^2)，空间复杂度为 O(1)。