Manacher's algorithms（马拉车算法）最长回文子串

太过爱你忘了你带给我的痛 2023-05-31 04:58 20阅读 0赞

# 最长回文子串 #

> https://leetcode-cn.com/problems/longest-palindromic-substring/

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
    输出: "bb"

## Manacher’s algorithm ##

核心思想：通过插入其他的字符，将回文串变为奇回文串。奇回文串一定存在一个中心点`loc`，对应的有一个半径`p[loc]`。从左往右遍历，关于每个节点都用**扩张法（也就是不断判断两边的边缘是否相同，相同则不断增加）** 来得到以它为中心的最长回文子串的边界长度来更新所对应的`p[i]`。然后，记录下当前 **边界最右** 的回文子串（即，记录下中心位置`loc`,以及对应的边界`mx`）。注意一个非常重要的细节：对于在当然记录下的`loc`右边的点，明显由于奇回文串的对称性， **能够知道该店关于`loc`的对称点的半径长度的最小值`p[2* loc -i]`** 。而当然，它也会受到边界`mx`的限制，**在`i`和`mx`之间的点，由于对称点的信息基本可以保证不用判断，就算需要判断，但是由于对称性，落入其中一定是因为不能再扩张了，（这点保证了算法时间复杂度被约束在了O(n)）** ，而在`mx`以外的点，仍然需要用扩张法来扩张对应的半径，（这样虽然是二重循环，但是，第二重只是对于`mx`以外的点进行了判断，因此仍然是O(n）。

## 代码 ##

#define min(x, y) ((x)>(y)?(y):(x))
    
    class Solution { 
    public:
    	string regenerate_str(string s) {  // 插入
    		string t("#");
    		int count=0;
    		for (int i = 0; i < s.size() * 2 + 1; ++i) { 
    			if (i % 2 == 0) {  t += s[count++]; }
    			else t += "#";
    		}
    		return t;
    	}
    
    	string longestPalindrome(string s) { 
    		if (s.size() < 2) return s;
    		s = regenerate_str(s);
    
    		int p[2002], start = 0, maxlen = 0;
    		int mx = 0, loc = 0;
    
    		for (int i = 0; i < s.size(); ++i) { 
    			if (i < mx && 2 * loc - i < s.size()) { 
    				p[i] = min(mx - i, p[2 * loc - i]);
    			}
    			else { 
    				p[i] = 1;
    			}
    
    			while (p[i] + i < s.size() && i - p[i] >= 0 && s[i - p[i]] == s[i + p[i]])
    				p[i] ++;
    
    			if (i + p[i] > mx) { 
    				mx = i + p[i];
    				loc = i;
    			}
    
    			if (p[i] > maxlen) {  maxlen = p[i]; start = i; }
    		}
    		s = s.substr(start - p[start] + 1, 2 * p[start] - 1);
    		string t;
    		for (int i = 0; i < s.size(); ++i) { 
    			if (s[i] != '#') t.push_back(s[i]);
    		}
    		return t;
    	}
    };