Manacher's algorithms(マラアルゴリズム)最長回文サブストリング

最長回文子列
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;
	}
};