[백준/C++] 1305번 광고

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

1305번: 광고

이 문제는 실패함수만 구해주면 수월하게 풀리는 문제이다.

bfs, dfs, 다익스트라를 공부할 때 코드의 틀을 외우듯이 실패함수도 외우고 계속 써먹다보면 언젠가 이해가 되리라 생각한다.

실패함수를 구한 뒤, 문제에서 주어진 광고판의 크기에서 실패함수를 빼주면 되는데, 광고판의 크기가 5라면 5번째 실패함수의 값을 빼주면 된다. (인덱스니까 -1해주기)

쉽게 말해서, 6칸짜리 광고판에 4글자 문구를 띄우면, 2칸이 남고 이 2칸은 4글자짜리 문구의 앞2 글자에서 따온다.

-> 6글자에서 겹치는 부분 분자열을 제거 = 원래 광고하려던 문구

 

비슷한 문제로는 https://www.acmicpc.net/problem/16900 가 있다.

16900번도 역시 kmp인데, 아래코드에서 cout << ~~~ 부분만 수정해주면 되니 잘 생각해보시길!!

cout << ((long long)k-1)*(s.length()-fail[s.length()-1])+s.length();

설명 : 문자열 s의 길이에서 최대로 겹치는 부분을 빼고, 이를 k-1번만 곱해준다. 그리고 s의 길이를 더해줌

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int fail[1000000];

void failure(string str){
    int j=0;
    // pi 배열은 접두사 접미사가 일치하는 최대 길이 구하기
    for(int i = 1; i < str.size() ; i++){
        while(j > 0 && str[i] != str[j]) { // 다르면
            j = fail[j - 1]; // 일치하는 부분까지 인덱스를 앞당김
        }
        if(str[i] == str[j]) {
            fail[i] = ++j; // 접두 접미사가 일치하는 최대 길이 저장
        }
        else{
            fail[i]=0;
        }
    }
}

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

    int l;
    string s;
    cin >> l >> s;
    failure(s);

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