回文子串

题目描述：

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”
示例 2：

输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示：

1 <= s.length <= 1000
s 由小写英文字母组成

思路:

使用马拉车算法，时间复杂度o（n），动态维护左边界和右边界

代码:

func countSubstrings(s string) int {
   n := len(s)
   t := "$#"
    for i:=0; i<n; i++{
        t+=string(s[i])+"#"
    }
    n = len(t)
    t+="!"
    dp := make([]int, n)
    iMax,rMax,ans := 0,0,0

    for i:=1;i<n;i++{
        if rMax >=i{
            dp[i] = min(rMax-i+1, dp[iMax*2-i])
        }else{
            dp[i] = 1
        }
        for t[dp[i]+i] == t[i-dp[i]]{
            dp[i] = dp[i]+1
        }
        if i+dp[i] -1 >rMax{
            iMax = i
            rMax = dp[i]+i-1

        }
        ans += dp[i]/2
    }
    return ans
}

func min(a , b int)int{
    if a>b{
        return b
    }
    return a
}

代码效率：

执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：4.7 MB, 在所有 Go 提交中击败了10.15%的用户