global round #7 D2 - Prefix-Suffix Palindrome (실패함수, prefix function)

https://codeforces.com/contest/1326/problem/D2

 

<문제설명>

문자열 s가 주어질 때, s의 prefix a, suffix b를 이어붙여 만들 수 있는 최대길이 팰린드롬을 출력하라.

(단, a+b<=s)

 

<풀이>

문자열 s의 prefix 중 최대 길이의 팰린드롬은 어떻게 구할까?

s를 뒤집은 문자열을 t라고 하고

string a = s + "#" + t;

 

a의 pref[a.size()-1]이 그 팰린드롬의 최대길이이다.

 

prefix function pref

pref[i] : i로 끝나는 문자열에서 suffix==prefix 최대길이

pref.resize(t.size());
for (int i = 1, j = 0; i < t.size(); i++) {
	while (j > 0 && t[i] != t[j]) j = pref[j - 1];
	if (t[i] == t[j]) pref[i] = ++j;
}

 

<코드>

int tt;
string inp;
string prefixPalin(string a) {
	string b = a;
	reverse(b.begin(), b.end());
	string s = a + "#" + b;	//더미문자 추가해서 s길이 홀수로 강제

	vector<int> pref(s.size());
	int j = 0;
	for (int i = 1; i < s.size(); i++) {
		while (j > 0 && s[i] != s[j]) j = pref[j - 1];
		if (s[i] == s[j]) pref[i] = ++j;
	}

	return a.substr(0, j);
}
int main() {
	FAST; cin >> tt;
	while (tt--) {
		cin >> inp;
		int lo = 0;
		while (lo < (int)inp.size()-lo-1 && inp[lo] == inp[inp.size() - 1 - lo])
			lo++;

		if (lo > 0)
			cout << inp.substr(0, lo);

		string s = inp.substr(lo, inp.size() - 2 * lo);
		string a = prefixPalin(s);
		reverse(s.begin(), s.end());
		string b = prefixPalin(s);
		if (a.size() < b.size()) swap(a, b);
		cout << a;

		if (lo > 0)
			cout << inp.substr(inp.size() - lo, lo);
		cout << '\n';
	}
}