(백준 알고리즘 문제풀이) 1305번 광고

문제

문제 링크

문제 접근

• 이 문제는 make_pi를 이용하면 쉽게 풀수 있는 문제이다.
• 접두사와 접미사가 같은 경우를 생각해보면, 현 문자열에서 접두사와 접미사가 최대로 같을 때 그 길이를 빼면 광고 문구를 구할 수 있다.
• 예를 들어 aaaaa 같은 경우, 최대로 같은 경우는 접두사가 aaaa고 접미사가 aaaa인 경우로 4개 이다.
• 이때 그럼 광고 문구는 a로 1이 정답이 된다.
• aabaaa라면 접두사와 접미사가 같은 최대로 같은 경우는 aa로 가장 짧은 광고 문구는 aaba가 된다.

코드

#include <iostream>
using namespace std;
int n, pi[1000001];
char s[1000001];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>s;
    int j = 0;
    for(int i = 1; i < n; i++){
        while(s[i] != s[j] && j > 0)j = pi[j-1];
        if(s[i] == s[j])pi[i] = ++j;
    }
    cout << n - pi[n-1];
}

느낀점

• KMP를 이해하기 있으니 make_pi를 활용할 방법도 떠올랐다.
• 몰랐다면 절대 풀지 못했을 것 같다. 풀 수 있음에 감사하다.