📌Manacher's Algorithm

문자열의 모든 위치에 대해서 그 위치를 중심으로 하는 최대 길이의 팰린드롬 을 찾아내는 알고리즘이다.

💿 팰린드롬 (Palindrome)?

한국어로 회문 이라고 한다.
순방향으로 읽었을 때와 역방향으로 읽었을 때가 같은 문자열을 의미한다.

💿 시간 복잡도

해당 알고리즘은 O(n) 의 시간 복잡도를 보장한다.
다른 팰린드롬 찾기 알고리즘들에 비해 훨씬 효율적인 시간 복잡도를 갖는다.

💿 장점

1. 시간 복잡도가 O(n) 으로 팰린드롬 찾기 알고리즘 중 가장 빠른 시간 복잡도를 가지고 있다.

💿 단점

1. 홀수 길이의 팰린드롬만 찾을 수 있다.
2. 해당 알고리즘을 통해 구해지는 결과 값이 팰린드롬의 한쪽 길이만 구하기 때문에 값이 직관적이지 않을 수 있다.

💿 코드 구현

int ManacherAlgorithm(string _str)
{
	//Manacher's Algorithm은 짝수 길이의 팰린드롬의 길이를 구할 수 없다.
    //해당 문제점을 보완하기 위해 더미 문자를 삽입하는 과정이 필요하다.
	string tmpStr = "";
	for (int i = 0;i < _str.size();i++)
	{
		tmpStr += _str[i];
		tmpStr += ".";
	}
	_str = tmpStr;

	int size = _str.size();
	vector<int> radius(size, 0);	//i 번째 위치를 중심으로 하는 팰린드롬의 최장 길이를 저장
	int rightIdx = 0;				//최장 팰린드롬의 우측 끝 인덱스
	int centerIdx = 0;				//최장 팰린드롬의 중심 인덱스

	for (int i = 0;i < size;i++)
	{
		///현재 위치의 글자가 최장 팰린드롬의 범위 내에 있는 경우
		///현재 위치의 글자가 팰린드롬의 우측 범위에 있다는 뜻이고
		///해당 위치의 radius 값은 대칭되는 좌측 범위에서 구해진 값과 동일하기 때문에
        ///현재 위치와 대칭되는 radius 값을 저장하고 넘어간다.
		if (i <= rightIdx)
		{
			radius[i] = min(radius[2 * centerIdx - i], rightIdx - i);
		}

		//i번째 위치를 중심으로 뻗어나가면서 두 문자가 일치하는지 확인
		while (true)
		{
			//확인하는 위치가 문자열의 범위를 벗어나지 않는지 체크
			if (i - radius[i] - 1 < 0)
				break;

			if (i + radius[i] + 1 >= size)
				break;

			//현재 비교하고 있는 두 문자가 같은지 체크
			if (_str[i - radius[i] - 1] != _str[i + radius[i] + 1])
				break;

			//두 문자가 같은 경우에만 팰린드롬의 길이를 늘린다.
			radius[i]++;
		}

		///기존보다 더 긴 팰린드롬이 발견되었다면
		///rightIdx와 centerIdx 값을 갱신한다.
		if (rightIdx < i + radius[i])
		{
			rightIdx = i + radius[i];
			centerIdx = i;
		}
	}

	//찾아낸 팰린드롬의 길이 중 가장 긴 값을 반환한다.
	return *max_element(radius.begin(), radius.end());
}

결과

banana 에서 가장 긴 팰린드롬은 anana 로 길이는 5 이다.
apple 에서 가장 긴 팰린드롬은 pp 로 길이는 2 이다.

코드 추가 해설

코드 내에서 '현재 위치의 글자가 최장 팰린드롬의 범위 내에 있는 경우' 는 다음과 같다.