前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 5 Longest Palindromic Substring

Leetcode 5 Longest Palindromic Substring

作者头像
triplebee
发布2018-01-12 15:19:36
5390
发布2018-01-12 15:19:36
举报
文章被收录于专栏:计算机视觉与深度学习基础

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

求最长回文子串的裸题,搞竞赛的时候遇到过各种花样的变式。

n方的朴素算法已经烂大街了,推荐使用O(n)的算法,只可惜很久没用过manacher算法,不会写了,所以花了一段时间温故知新。

manacher算法原理不了解的道友可以看这篇文章:

https://cloud.tencent.com/developer/article/1019346

点击打开链接

代码语言:javascript
复制
class Solution 
{
public:
    string init(string s)
    {
        string result("*#");//防止越界
        for(int i=0;i<s.length();i++)
        {
            result+=s[i];
            result+='#';
        }
        result+='&';
        return result;
    }
    string longestPalindrome(string s) 
    {
        string ch=init(s);
        int p[2010],id=0,maxlen=0,pos=0;
        p[0]=0;
        for(int i=1;i<ch.length();i++)
        {
            if(p[id]+id>i)
                p[i]=min(p[2*id-i],p[id]+id-i); 
            else
                p[i]=1;
            while(ch[i-p[i]] == ch[i+p[i]])
                p[i]++;  
            if(id+p[id]<i+p[i])
                id=i;  
            if(maxlen<p[i])
            {
                pos=i;
                maxlen=p[i];
            }
        }
        pos/=2;
        string result=s.substr(pos-maxlen/2,maxlen-1);
        return result;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-08-24 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档