백준 16900번 - 이름 정하기

백준 16900번 - 이름 정하기

www.acmicpc.net/problem/16900

16900번: 이름 정하기

KMP 알고리즘 문제이다.

사실 KMP라 하기도 조금 아쉽지만 어쨌든 Pi (접두사 == 접미사 인 최장길이)만 사용하면 해결 가능하다.

 

계속해서 더해갈 건데 이때 pi가 중요하다.

이유는 접두사==접미사 라면 그만큼의 길이를 빼고 더해줘야 한다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
vector<int>getPartialMatch(const string& N) {
    int m = N.size();
    vector<int>pi(m, 0); 
    int begin = 1, matched = 0;
    while (begin + matched < m) {
        if (N[begin + matched] == N[matched]) {
            ++matched;
            pi[begin + matched - 1] = matched;
        }
        else {
            if (matched == 0) {
                ++begin;
            }
            else {
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return pi;
}
 
int main() {
    int k;
    string str;
    cin >> str >> k;
    vector<int>pi = getPartialMatch(str);
    int size = str.size();
    long long ans = size;
    for (int i = 1; i < k; i++) {
        ans += size - pi[size - 1];
    }
    cout << ans << "\n";
}

ans의 자료형이 long long임에 주의하자