백준 1305 (광고) c++

문제

1305번: 광고

처음에 문제를 이해하지 못해 함참을 고민한 문제입니다.

광고판의 길이 L이 주어지면 광고판에는 어떤 광고가 무한히 반복적으로 나타납니다.

그때 광고판에 표시된 문자열에서 최소길이의 광고의 길이를 구하는 문제입니다.

 

예를 들어 광고판 L의 길이가 5이고 주어진 문자열이 babba라면 여기서 연속적으로 광고가 될 수 있는 

문자열의 최소길이를 구하는 것입니다.

babba (bab가 연속적으로 나타나기 때문에 광고가 가능한 최소 문자열의 길이는 3입니다.

 

다른 예시로 광고판 L의 길이가 6이고 주어진 문자열이 babbac라면 여기서 연속적으로 광고가 될 수 있는

문자열의 최소길이는 6입니다.

babbac 맨 마지막 글자인 c를 광고에 포함하지 않으면 영원히 광고판에 등장하지 않기 때문입니다.

 

이를 통해 알 수 있는 사실은 KMP알고리즘에서 사용하는 fail 배열을 통해 주어진 배열에 대해서

접두사와 접미사와 겹치는 정보를 저장하고

전체 문자열에서 fail[맨 마지막 글자] 를 빼주면 광고의 최소 길이가 됩니다.

 

광고가 될 수 있는 최대 길이는 전체 문자열의 길이 입니다.그중에서 맨 마지막 fail[맨 마지막 글자]의 의미는 맨 마지막 글자의 접두사 접미사와 겹치는 부분의 길이입니다.따라서 그 둘을 빼게 되면 광고가 될 수 있는 최소 길이가 나옵니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll fail[10000001];
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n;
	cin >> n;
	string s;
	cin >> s;
	for (int i = 1, j = 0; i < n; i++) {
		while (j > 0 && s[i] != s[j])j = fail[j - 1];
		if (s[i] == s[j])fail[i] = ++j;
	}
	if (fail[n - 1])cout << n - fail[n - 1];
	else cout << n;
	return 0;
}