[백준/BOJ] 백준 1305번 : 광고

www.acmicpc.net/problem/1305

1305번: 광고

KMP알고리즘의 pi를 구해서 문제를 해결했다. 만들어진 pi를 이용하여, 전체 문자열에서 접두사와 접미사가 같은 최대 문자열의 접두사 문자열 하나 제거한 문자열의 길이를 출력했다.

 

코드

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

//알고리즘 문제해결 전략2 책 KMP 알고리즘 공부 실습
//KMP알고리즘의 pi를 구해서 문제를 해결
int L;
string input;
vector<int> pi(1000000, 0);

void Make_pi()
{
	int start = 1;
	int matched = 0;

	while (start + matched < L)
	{
		if (input[matched] == input[start + matched])
		{
			matched++;
			pi[start + matched - 1] = matched;
		}

		else
		{
			if (matched == 0)
			{
				start++;
				matched = 0;
			}

			else
			{
				start += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> L;
	cin >> input;

	Make_pi();

	cout << L - pi[L - 1]; //전체 문자열에서 접두사와 접미사가 같은 최대 문자열의 접두사 문자열 하나 제거한 문자열의 길이

	return 0;
}