最长回文子串（Longest Palindromic Substring）

红太狼 2022-06-09 04:26 168阅读 0赞

Leetcode 5. Longest Palindromic Substring

Description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"
    
    Output: "bab"
    
    Note: "aba" is also a valid answer.

Example:

Input: "cbbd"
    
    Output: "bb"

根据题目要求，要求s中的最长回文子串

最简单的思路是求出s的所有子串，判断是不是回文，记录下最长的那一个。

string LongestPsub(string s)
    {
    	int start = 0;
    	int max = 0;
    	int len = s.size();
    	for (int i = 0; i < len; i++)
    	{
    		for (int j = i + 1; i < len; j++)
    		{
    			int temp1, temp2;
    			for (temp1 = i, temp2 = j; temp1 < temp2; temp1++, temp2--)
    			{
    				if (s.at(temp1) != s.at(temp2))
    					break;
    			}
    			if (temp1 >= temp2 && i - j + 1 > max)
    			{
    				start = i;
    				max = i - j + 1;
    			}
    		}
    	}
    	return s.substr(start, max)
    }

但是以这样的方法时间复杂度是O(n^3)，时间过长无法通过提交。

之后采用中心扩展，即将每一个字符当做中心向两边扩展，寻找最长回文，时间复杂度为O(n^2)，但要注意区分回文串是奇、偶两种情况。

string LongestPsub(string s)
    {
    	int start = 0;
    	int max = 0;
    	int len = s.size();
    	for (int i = 0; i < len; i++)
    	{
    		int j = i;
    		int k = i;
    		while(j >= 0 && k < len && s.at(j) == s.at(k))
    		{
    			if (k - j + 1 > max)
    			{
    				start = j;
    				max = k - j + 1;
    			}
    			k++;
    			j--;
    		}
    		
    	}
    
    	for (i = 0; i < len; i++)
    	{
    		int j = i - 1;
    		int k = i + 1;
    		while(j >= 0 && k < len && s.at(j) == s.at(k))
    		{
    			if (k - j + 1 > max)
    			{
    				start = j;
    				max = k - j + 1;
    			}
    			k++;
    			j--;
    		}
    		
    	}
    	return s.substr(start, max);
    }

该方法通过提交。

当然最长回文子串还有其他方法，留个坑等掌握了再来填。

\----------------------------------------------------------------------------------------------------------------------------------------------------------  
更新Manacher算法，果然有名字的算法都不太好理解.......

string Manacher(string s)
    {
    	//添加'#'
    	int len = s.size();
    	for (int i = 0, k = 1; i < len - 1; i++)
    	{
    		s.insert(k, "#");
    		k += 2;
    	}
    	len = len + len - 1;
    	//Manacher
    	int *rad = new int[len];
    	rad[0] = 0;
    	int j;
    	for (i = 1, j = 1, k; i < len; i = i + k)
    	{
    		while (i - j >= 0 && i + j < len && s.at(i - j) == s.at(i + j))
    		{
    			j++;
    		}
    		rad[i] = j - 1;
    		for (k = 1; k <= rad[i] && rad[i-k] != rad[i] - k; k++)
    			rad[i + k] = min(rad[i - k], rad[i] - k);
    		j = max(j - k, 1);
    	}
    	//找出最长的回文
    	int max = 0;
    	int center;
    	for ( i = 0; i < len; i++)
    	{
    		if (rad[i] > max)
    		{
    			max = rad[i];
    			center = i;
    		}
    	}
    	string tar = s.substr(center - max, 2 * max + 1);
    	//去掉'#'
    	string ::iterator it;
    	for (it = tar.begin(); it != tar.end(); )
    	{
    		if ( *it == '\#')
    		{
    			tar.erase(it);
    		}
    		else ++it;
    	
    	}
    	return tar;
    }