题解 | #最长回文子串#

最长回文子串

https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af

马拉车算法

注释已经写下大致思路

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    int getLongestPalindrome(string s) {
        // write code here
        int n = s.size();
        vector<int> d1(n, 0), d2(n, 0);
        int a1 = 0, a2 = 0;
        // 考虑以i为中心,半径为d1[i]的奇数长度回文串
        for(int i = 0, l = 0, r = -1; i < n; i++)
        {
            // 当i<=r, 即i在已确认的“外部”回文串s[l..r]时,
            // 显然[l..r]有一个与i对称的j = l + r - i, 显然j < i
            // 如果以j为中心的回文串的左边界大于等于l,则d1[i]显然等于d1[i]
            // 即使使用暴力扩展, 也不可能出现回文串长度增大的情况
            // 如果以j为中心的回文串的左边界小于l
            // 那么可确定的以i为中心的字符串半径是r - i + 1, 可能会更大
            // 因而需要使用暴力去扩展i为中心的字符串
            int k = (i > r ? 1 : min(d1[l + r - i], r - i + 1));
            while(i >= k && i + k < n && s[i - k] == s[i + k]){
                k++;
            }
            d1[i] = k--;
            a1 = max(a1, d1[i]);
            // 始终需要维护右边界最靠右的回文串
            if(i + k > r)
            {
                r = i + k;
                l = i - k;
            }
        }
        // 偶数长度回文串类似
        for(int i = 0, l = 0, r = -1; i < n; i++){
			// 一个比较绕的地方在于,偶数长度回文串取(l + r) / 2 + 1作为回文中心
			// 因而,j = l + r - i虽然在[l..r]与i对称,但以j为回文中心的串和以i为回文中心的串并不对称
		  	// 作为回文中心,i与j + 1才是对应的
            int k = (i > r ? 0 : min(d2[l + r - i + 1], r - i + 1));
            while(i >= k + 1 && i + k < n && s[i - k - 1] == s[i + k]){
                k++;
            } 
            d2[i] = k--;
            a2 = max(a2, d2[i]);
            if(i + k > r)
            {
                r = i + k;
                l = i - k - 1;
            }
        }
        return max(2 * a1 - 1, 2 * a2);
    }
};

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
牛客38347925...:9,2学生暑期实习失利开始投小厂,给这群人整自信了
点赞 评论 收藏
分享
06-15 20:57
已编辑
门头沟学院 Java
CARLJOSEPH...:年轻人有傲气很正常,但是建议工作前洗净傲气。 说实在的,什么奖学金什么奖项的都很一般。尊重你的老师,在有时间的时候去上课,真遇到走不开的事,请态度端正地向你的老师说明情况,请求请假。我相信任何一个有师德的老师都会允许的(我的老师就是这样)。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务