광고
문제 해석
- 가장 짧은 광고 길이를 구하는 문제입니다.
- 광고업자는 길이가 N인 광고를 무한히 붙여서 광고합니다.
설계(X)
- KMP알고리즘의 실패함수를 이용하는 문제입니다.
- 우선 KMP알고리즘의 개념을 파악하기 위해서 멍멍멍님 블로그, crocus님 블로그 을 활용하였습니다.
- 실패함수란, “접두사(prefix)==접미사(suffix)가 될 수 있는 최대 길이 부분 문자열”입니다.
- 자신을 제외한 인덱스 1부터 접두사와 접미사가 일치한 지 비교하여 최대값을 갱신해줍니다.O(M)
- 해당 문제의 정의는 “가능한 최소의 광고길이는 문자열의 길이에서 접두사와 접미사가 같은 최대 길이를 뺀 값”입니다.
- 사실, 위의 정의를 이해하기가 쉽지 않았습니다.
- 광고는 어떤 패턴이 연속으로 이어져 있기 때문에 앞에서 나온 패턴이 뒤에서도 나오게 됩니다.
- 이 뜻은, 접미사가 앞에 있는 접두사와 같은 길이의 패턴으로 이어져 있다는 것입니다.
- 예를들어, aabaaa인 문자열은 “aaba”에 앞의 prefix인 “aa”를 더해서 만들어진 것으로, prefix와 suffix의 최대 공통 길이를 찾으면 해당 길이가 원래 광고의 prefix가 됩니다.
- 최종적으로 문자열의 길이에서 원래 광고의 prefix를 제거하면 원하는 길이를 얻을 수 있습니다.
구현(X)
코드
#include <iostream>
#include <vector>
using namespace std;
string s;
int N;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> s;
vector<int> pi(N,0);
int j = 0;
for (int i =1;i< N; i++){
while (j>0 && s[i]!=s[j]) j = pi[j-1];
if (s[i] == s[j]){
pi[i] = ++j;
}
}
cout << N - pi[N-1] <<"\n";
return 0;
}
디버깅
제출결과
- 12 ms
마무리
- 해당 문제는 KMP 알고리즘의 실패함수를 이용하는 문제였습니다.
- KMP알고리즘 자체를 이해하기가 어려웠으나 위에서 언급한 분들의 블로그 덕분에 이해할 수 있었습니다.