[BOJ] 1305 광고

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

 

 

문제 풀이:

 

fail함수를 작성해서 prefix와 suffix가 일치하는 가장 긴 길이를 찾는다. 그 값을 광고판에 보이는 문자열 길이인 l에서 빼주면 된다.

여기서 중요한 점은 fail 함수에서 가장 큰 값을 빼주는 것이 아니라 맨 뒤를 기준으로 prefix와 suffix를 구해줘야 한다.

예를 들어, 입력으로 aaabaaadaa가 들어온다고 하자. fail[6]=3으로 가장 큰 값을 가지지만 결과는 맨 앞 뒤 aa만 겹치는 것으로 봐야 하므로 output은 8이다.

 

 

소스 코드:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>

using namespace std;

int l;
char arr[1000002];
int fail[1000002];

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

	cin >> l;
	cin >> arr;

	for (int i = 1, j = 0; i < l; i++) {
		while (j > 0 && arr[i] != arr[j]) j = fail[j - 1];
		if (arr[i] == arr[j]) fail[i] = ++j;
	}

	cout << l - fail[l-1] << '\n';
	return 0;
}