백준 - 1305 광고

문제 링크입니다 : https://www.acmicpc.net/problem/1305

1305번: 광고

KMP 문제이다.

 

failure function 이용하면 쉽게 풀수 있는 문제였다! 물론 난 많이 틀렸다.. ㅋㅋㅋㅋ

 

 

 

 

 

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> getPi(string p) {
    int m = p.size();
    int j = 0;
    vector<int> pi(m, 0);

    for(int i = 1; i < m; i++) {
        while(j > 0 && p[i] != p[j]) {
            j = pi[j - 1];
        }
        if(p[i] == p[j]) {
            pi[i] = ++j;
        }
    }
    return pi;
}

int main() {
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);
    int N;
    cin >> N;
    string str;
    cin >> str;
    vector<int> pi = getPi(str);

    cout << pi.size() - pi.back();

    return 0;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~