题目描述

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

样例

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

算法1

(区间dp) $O(n^2)$

本题求最长回文子串，考虑回文的特点，一个串是回文等价于两边字符相等，且去掉两边字符后中间串仍是回文串，因此可以使用区间dp来做。

定义bool类型f[i][j]为目标串从i到j是否为回文串，初始定义f[i][i]都为true，然后按照区间dp的套路做就行了。

时间复杂度

参考文献

Golang 代码

func longestPalindrome(s string) string {
    n := len(s)
    f := make([][]bool, n)
    for i := range f {
        f[i] = make([]bool, n)
        f[i][i] = true
    }
    for step := 2; step <= n; step++ {
        for i := 0; i <= n-step; i++ {
            j := i+step-1
            f[i][j] = s[i] == s[j] && ((i+1 <= j-1 &&f[i+1][j-1]) || i+1 > j-1)
        }
    }
    for step := n; step >= 1; step-- {
        for i := 0; i <= n-step; i++ {
            j := i+step-1
            if f[i][j] {
                return s[i:j+1]
            }
        }
    }
    return ""
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

算法2

(马拉车算法) $O(n)$

blablabla

时间复杂度

参考文献

Golang 代码

func longestPalindrome(s string) string {
    n := len(s)
    mana := make([]byte, 2*n+1)
    for i := 0; i < n; i++ {
        mana[2*i] = '*'
        mana[2*i+1] = s[i]
    }
    mana[2*n] = '*'
    radis := make([]int, 2*n+1)
    var lim, last int
    res := 0
    resIdx := 0
    var resstr []byte
    for i := 0; i < 2*n+1; i++ {
        if i < lim {
            radis[i] = min(radis[2*last-i], lim-i)
        }
        k := 1
        for i + k < 2*n+1 && i-k >= 0 {
            if mana[i+k] == mana[i-k] {
                radis[i]++
                k++
            } else {
                break
            }
        }
        if radis[i] > lim {
            lim = radis[i]
            last = i
        }
        if res < radis[i] {
            res, resIdx = radis[i], i
        }

    }
    //fmt.Println(res, resIdx)
    for k := resIdx-res; k <= resIdx+res; k++ {
        if mana[k] != '*' {
            resstr = append(resstr, mana[k])
        }
    }
    return string(resstr)
}
func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}