首页 > 代码库 > Manacher算法--O（n）内求回文子串

Manacher算法--O（n）内求回文子串

2024-07-07 04:59:00   227人阅读


昨天做了leetcode里的     Longest Palindromic Substring ，一开始用动态规划O(N^2),不管怎么改都超时了。。。于是在大神的帮助下，找到了传说中的Manacher算法，居然能在O（n）内求出来，瞬间给跪了。

本屌认为，这个算法主要是充分的利用了以前的匹配的结果，来起到了降低时间复杂度的作用，这点跟KMP算是有点类似。在预处理时有个小技巧就是将第0,1为设为"$#",后面每隔一位加一个“#”,这样既能够防止数组越界问题又能够，避免奇数和偶数的讨论。如 aaaa 就变成 $#a#a#a#a#

这是核心部分代码：

void Manacher(int n)
{
    int mx=0;
    int id;
    p[0]=0;
    for(int i=1;i<n;i++)
    {
        p[i]=1;
        if(mx>i)
        {
            p[i]=min(p[2*id-i],mx-i);
        }
        while(str[i-p[i]]==str[i+p[i]]) p[i]++;
        if(i+p[i]>mx)
        {
            id=i;
            mx=i+p[i];
        }
    }
}

P［i］记录的是以字符str［i］为中心的最长回文串的半径。且这里有一个很好的性质，P［i］-1就是该回文子串在原串中的长度（包括‘#’）

举个例子：         

    原串：    w aa bwsw f d
    新串：   # w# a # a # b# w # s # w # f # d #
辅助数组P：  1 2 1 2 3 2 1 2 1 2 1 4 1 2 1 2 1 2 1


接下来就是关键部分了，如何运用前面的结果

        if(mx>i)
        {
            p[i]=min(p[2*id-i],mx-i);
        }


接下来就借用下大神的图了

有两种情况








下附上某大牛的地址：http://blog.csdn.net/ggggiqnypgjg/article/details/6645824

这个是题目链接：https://oj.leetcode.com/problems/longest-palindromic-substring/


Longest Palindromic Substring

 Total Accepted: 11893 Total Submissions: 58709My Submissions

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.

Have you been asked this question in an interview?

这个是AC的：
class Solution {
private:
	string stmp;
	string init(string s)
	{
		string ret="$";
		for(int i=0;i<s.size();i++)
		{
			ret+="#"+s.substr(i,1);
		}
		ret+="#";
		return ret;
	}
	void Manacher(int len,string str,int *p)
	{
		int mx=0;
		int id;
		p[0]=0;
		for(int i=1;i<len;i++)
		{
			
			p[i]=1;
			if(mx>i)
			{
				p[i]=min(p[2*id-i],mx-i);
			}
			while(str[i-p[i]]==str[i+p[i]]) p[i]++;
			if(i+p[i]>mx)
			{
				id=i;
				mx=i+p[i];
			}
		}
	}
public:
    string longestPalindrome(string s) 
    {
        string str=init(s);
        int *p=new int[str.size()];
        Manacher(str.size(),str,p);
        int ans=0,index=0;
        for(int i=1;i<str.size();i++)
        {
        	if(p[i]>ans)
        	{
        		ans=p[i];
        		index=i;
        	}
        }
        delete []p;
        return s.substr((index-ans)/2,ans-1);
    }
};

这个是动态规划的，跟网上的大同小异，不过超时了：
class Solution {
public:
    string longestPalindrome(string s) 
    {
        int m=1,beg=0,end=0;
        int len=s.size();
        bool flag[len][len];
        for(int i=0;i<len;i++)
        	for(int j=0;j<len;j++)
        	{
        		if(i>=j) flag[i][j]=true;
        		else flag[i][j]=false;
        	}
        for(int j=1;j<len;j++)
        	for(int i=0;i<j;i++)
        	{
        		if(s[i]==s[j])
        		{
        			flag[i][j]=flag[i+1][j-1];
        			if(flag[i][j]&&j-i+1>m)
        			{
        				beg=i;
        				end=j;
        				m=j-i+1;
        			}
        		}
        		else
        			flag[i][j]=false;
        	}
        return s.substr(beg,m);
    }
};


联系
我们