(BOJ) 14444 가장 긴 팰린드롬 부분 문자열

문제: https://www.acmicpc.net/problem/14444

 

문제 풀이:

manacher 알고리즘 이용

 

A[i] : i번째 문자를 중심으로 가능한 회문의 길이(반지름)

 

S=baab 이런 경우 어떤 문자를 기준으로 해도 회문을 찾을 수 없으므로 

'#'을 추가해 준다 -> S=#b#a#a#b#

 

ex) S=#b#a#a#b#

i	0	1	2	3	4	5	6	7	8
A[i]	0	1	0	1	4	1	0	1	0

r: (가장 긴) 회문의 길이 + 해당 위치의 인덱스

p: (가장 긴) 회문의 길이를 가지는 중심축의 위치

2*p-i: p를 중심으로 i의 회문에서의 대칭점

 

i<=r 이라는 말은 현재 위치의 문자가 회문에 속한다는 말이다.

 

 

소스 코드:

int A[100001 * 2];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	
	string s;
	cin >> s;

	string s2="";
	for (int i = 0; i < s.size(); i++) {
		s2 += '#';
		s2 += s[i];
	}
	s2 += '#';
	int len=s2.size();
	int r=0,p=0,res=0;
	
	for (int i = 0; i < len; i++) {
		if (i <= r) A[i] = min(A[2 * p - i], r - i);
		
		while (i - A[i] - 1 >= 0 && i + A[i] + 1 < len &&s2[i - A[i] - 1] == s2[i + A[i] + 1]) A[i]++;

		if (i + A[i] > r) {
			r = i + A[i];  
			p = i;
		}
	}
	for (int i = 0; i < len; i++) res = max(res, A[i]);
	cout << res << '\n';
	return 0;
}