题目0647:回文子串

题目描述

给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。

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

示例1:

输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".

示例2:

输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

注意:输入的字符串长度不会超过1000。

解题技巧

• 方法一:从中心往两侧延伸

在长度为N的字符串中,可能的回文串中心位置有2N-1个:字母或两个字母中间。

从每一个回文串中心开始统计回文串数量。回文区间[a, b]表示 S[a], S[a+1], ..., S[b]是回文串,根据回文串定义可知[a+1, b-1]也是回文区间。

算法:对于每个可能的回文串中心位置,尽可能扩大它的回文区间[left, right]。当left >= 0 and right < N and S[left] == S[right]时,扩大区间。此时回文区间表示的回文串为S[left], S[left+1], ..., S[right]。

class Solution(object):
    def countSubstrings(self, S):
        N = len(S)
        ans = 0
        for center in xrange(2*N - 1):
            left = center / 2
            right = left + center % 2
            while left >= 0 and right < N and S[left] == S[right]:
                ans += 1
                left -= 1
                right += 1
        return ans

复杂度分析

时间复杂度:$O(N^2)$,其中N表示字符串S的长度,每次扩大回文区间的需要时间O(N)。

空间复杂度:O(1)。

• 方法二:马拉车算法

马拉车算法可以在线性时间内找出以任何位置为中心的最大回文串。

算法

假设一个回文串中心为center,该中心对应的最大回文串右边界为right。存在一个i为当前回文串中心,满足i > center,那么也存在一个j与i关于center对称,可以根据Z[i]快速计算出Z[j]。

当i < right时,找出i关于center的对称点j = 2 * center - i。此时以i为中心,半径为right - i的区间内存在的最大回文串的半径Z[i]等于 Z[j]。

例如,对于字符串A = '@#A#B#A#A#B#A#＄',当center = 7, right = 13, i = 10时,center为两个字母A中间的#,最大回文串右边界为最后一个#,i是最后一个B,j是第一个 B。

在[center - (right - center), right]中,区间中心为center,右边界为right,i和j关于center对称,且Z[j] = 3,可以快速计算出 Z[i] = min(right - i, Z[j]) = 3。

在while循环中,只有当Z[i]超过right - i时,才需要逐个比较字符。这种情况下,Z[i]每增加1,right也会增加1,且最多能够增加2*N+2次。因此这个过程是线性的。

最后,对Z中每一项v计算(v+1) / 2,然后求和。假设给定最大回文串中心为C,半径为R,那么以C为中心,半径为R-1, R-2, ..., 0的子串也都是回文串。例如abcdedcba是以e为中心,半径为4的回文串,那么e，ded，cdedc，bcdedcb和abcdedcba也都是回文串。

除以2是因为实际回文串的半径为v的一半。例如回文串a#b#c#d#e#d#c#b#a的半径为实际原回文串半径的 2 倍。

def countSubstrings(self, S):
    def manachers(S):
        A = '@#' + '#'.join(S) + '#$'
        Z = [0] * len(A)
        center = right = 0
        for i in xrange(1, len(A) - 1):
            if i < right:
                Z[i] = min(right - i, Z[2 * center - i])
            while A[i + Z[i] + 1] == A[i - Z[i] - 1]:
                Z[i] += 1
            if i + Z[i] > right:
                center, right = i, i + Z[i]
        return Z

    return sum((v+1)/2 for v in manachers(S))

复杂度分析

时间复杂度:O(N),其中N是S的长度。根据上面分析,复杂度是线性的。

空间复杂度:O(N),数组A和Z的大小。