언제나 처음처럼

[문제 링크]

KMP 알고리즘이 활용되는 문제가 정말 많은거 같다.

금고를 반시계방향으로 돌려서 맞추는 횟수는 shifts(a, b) 함수의 반환값을 통해 알 수 있다.

돌리기 전 문자열을 a, 반시계 방향으로 돌리고 난 후 문자열을 b라고 했을 때 shifts(a, b) 를 수행하면 a문자열과 같은 문자열을 뒤에 붙인 문자열이 만들어지는데 이 문자열에서 b의 위치를 KMP 알고리즘을 통해 빠르게 구할 수 있다.

이 때 구한 b의 위치가 곧 돌린 횟수가 되므로 결과값에 누적시킨다.

문제를 해결하기 위해선 반시계방향, 시계방향으로 번갈아가며 돌려야 한다.

a문자열을 시계방향으로 돌려서 b문자열을 만드는데 돌리는 횟수와 b문자열을 반시계방향으로 돌려서 a문자열을 만드는 횟수가 같기 때문에 이를 이용하여 매개변수의 순서를 바꾼 shifts(b, a) 를 수행하면 동일한 결과를 얻을 수 있다.

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

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

	int begin = 1, matched = 0;
	while (begin + matched < len)
	{
		if (s[begin + matched] == s[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(const string& h, const string& s)
{
	int hLen = h.size(), sLen = s.size();
	int ret;
	vector<int> pi = getPartialMatch(s);

	int begin = 0, matched = 0;
	while (begin <= hLen - sLen)
	{
		if (matched < sLen && h[begin + matched] == s[matched])
		{
			matched++;

			if (matched == sLen)
			{
				ret = begin;
				break;
			}
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return ret;
}

int shifts(const string& original, const string& target)
{
	return KMPsearch(original + original, target);
}

int main(void)
{
	int tc;
	cin >> tc;

	while (tc--)
	{
		int N;
		cin >> N;

		vector<string> s(N+1);
		for (int i = 0; i <= N; i++)
			cin >> s[i];

		int sum = 0;
		for (int i = 0; i < N; i++)
		{
			if (i % 2 != 0)
				sum += shifts(s[i], s[i + 1]);
			else
				sum += shifts(s[i + 1], s[i]);
		}

		cout << sum << endl;
	}

	return 0;
}

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

[문제 링크]

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

[문제 링크]

입력받는 문자열 T, P의 최대 길이가 100만으로 굉장히 길기 때문에 O(NM) 알고리즘으로 풀 수 없다.

따라서 시간복잡도가 O(N+M)인 KMP-algorithm을 구현하여 풀었다.

추가로 공백을 포함하는 문자열을 입력받기 위해 cin 함수가 아닌 getline(cin, str) 함수를 사용하였다.

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

vector<int> getPartialMatch(const string& P)
{
	int Plen = P.length();
	vector<int> pi(Plen, 0);

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

	return pi;
}

vector<int> KMPsearch(const string& T, const string& P)
{
	int Tlen = T.length(), Plen = P.length();

	vector<int> pos;
	vector<int> pi = getPartialMatch(P);

	int begin = 0, matched = 0;
	while (begin <= Tlen - Plen)
	{
		if (T[begin + matched] == P[matched])
		{
			matched++;
			
			if (matched == Plen)
				pos.push_back(begin + 1);
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return pos;
}

int main(void)
{
	string T, P;

	getline(cin, T);
	getline(cin, P);

	vector<int> result = KMPsearch(T, P);

	cout << result.size() << endl;
	
	for (int i = 0; i < result.size(); i++)
		cout << result[i] << ' ';

	return 0;
}

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