Leetcode5最长回文子串

5最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-palindromic-substring 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

中心扩展算法
思路：根据回文字符串的对称性求解
时间复杂度：O(n2)
执行用时：16 ms
内存消耗：5.5 MB

void expandOdd(char *s, int s_len, int mid, int *l, int *r);
void expandEven(char *s, int s_len, int mid, int *l, int *r);

char *longestPalindrome(char *s)
{
    int start = 0, end = 0, mid = 0, left = 0, right = 0;
    int s_len = strlen(s);
    for (mid = 0; mid < s_len; mid++)
    {
        expandOdd(s, s_len, mid, &left, &right);
        if (right - left > end - start)
        {
            start = left;
            end = right;
        }
        expandEven(s, s_len, mid, &left, &right);
        if (right - left > end - start)
        {
            start = left;
            end = right;
        }
    }
    if (s_len > 0)
        s[end + 1] = '\0';
    return &s[start];
}

void expandOdd(char *s, int s_len, int mid, int *left, int *right)
{
    int l = mid - 1;
    int r = mid + 1;
    while (0 <= l && r <= s_len && s[l] == s[r])
    {
        l--;
        r++;
    }
    l++;
    r--;
    *left = l;
    *right = r;
}

void expandEven(char *s, int s_len, int mid, int *left, int *right)
{
    int l = mid;
    int r = mid + 1;
    while (0 <= l && r <= s_len && s[l] == s[r])
    {
        l--;
        r++;
    }
    l++;
    r--;
    *left = l;
    *right = r;
}

Solution 2

Manacher算法
时间复杂度：O(n)
执行用时：4 ms
内存消耗：6.3 MB

char *longestPalindrome(char *s)
{
    int s_len = strlen(s);
    int str_len = s_len * 2 + 1;
    char *str = (char *)malloc(str_len * sizeof(char));
    int *arr = (int *)malloc(str_len * sizeof(int));
    int mid = 0;
    int i = 0, l = 0, r = 0;
    int max_r = 0, center = 0;
    int max_pos = 0;
    for (i = 0; i < str_len; i++)
    {
        if (i % 2 == 0)
            str[i] = '#';
        else
            str[i] = s[i / 2];
    }
    for (mid = 0; mid < str_len; mid++)
    {
        if (2 * center - mid <= 0 || max_r - mid <= 0)
            arr[mid] = 0;
        else if (arr[2 * center - mid] < max_r - mid)
            arr[mid] = arr[2 * center - mid];
        else
            arr[mid] = max_r - mid;
        l = mid - arr[mid];
        r = mid + arr[mid];
        while (0 <= l && r < str_len && str[l] == str[r])
        {
            l--;
            r++;
        }
        l++;
        r--;
        arr[mid] = (r - l) / 2;

        if (arr[max_pos] < arr[mid])
            max_pos = mid;
        if (r > max_r)
        {
            max_r = r;
            center = mid;
        }
    }
    if (s_len > 0)
        s[max_pos / 2 + (arr[max_pos] + 1) / 2] = '\0';
    return &s[max_pos / 2 - arr[max_pos] / 2];
}