题解 | #密码截取#

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int mlc(string a) {
	string s = "^#";
	for (int i = 0; i < a.size(); i++) {
		s += a[i];
		s += "#";
	}
	s += "$";
	int zx = 0, right = 0, maxlen = 0;
	vector<int>len(s.size(), 0);
	for (int i = 1; i < s.size() - 1; i++) {
		len[i] = i < right ? min(len[2 * zx - i], right - i) : 1;
		while (s[i + len[i]] == s[i - len[i]])
			len[i]++;
		if (i + len[i] > right) {
			right = i + len[i];
			zx = i;
		}
		if (len[i] > maxlen)
			maxlen = len[i];
	}
	return maxlen - 1;
}

int main() {
	string s;
	cin >> s;
	cout << mlc(s) << endl;
	return 0;
}