알고스팟: 팰린드롬 만들기 (ID: PALINDROMIZE)

[문제 링크]

algospot.com :: PALINDROMIZE

---

KMP 알고리즘을 알기 전에는 팰린드롬 만들기 문제를 엄청 비효율적으로 풀었던거 같은데, KMP알고리즘을 배우면서 부분문자열의 접두사와 접미사가 일치하는 최대 길이를 효율적으로 구할 수 있게 되었다.

 

문자열 S와 이를 뒤집은 'S 문자열을 가지고 S의 접미사이면서 'S의 접두사가 되는 구간의 최대 길이를 찾은 다음, 문자열 S의 시작부분 부터 접미사가 시작되는 부분 전까지의 길이를 S 뒤에 붙여주면 가장 짧은 팰린드롬이 완성된다.

 

완성한 팰린드롬의 길이를 출력하면 원하는 결과를 얻을 수 있다.

---

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

vector<int> getPartialMatch(string& rS)
{
	int len = rS.size();
	vector<int> pi(len, 0);

	int begin = 1, matched = 0;
	while (begin + matched < len)
	{
		if (rS[begin + matched] == rS[matched])
		{
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return pi;
}

int KMPsearch(string& S)
{
	int len = S.size();
	string rS;

	for (int i = len - 1; i >= 0; i--)
		rS.push_back(S[i]);
	
	vector<int> pi = getPartialMatch(rS);

	int begin = 0, matched = 0, addLen = len;
	while (begin + matched < len)
	{
		if (matched < len && S[begin + matched] == rS[matched])
		{
			matched++;
			
			if (matched == len - begin)
			{
				addLen = begin;
				break;
			}
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return len + addLen;
}

int main(void)
{
	int tc;
	cin >> tc;
	
	while (tc--)
	{
		string S;
		cin >> S;
		cout << KMPsearch(S) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 138 day