BOJ 1305 광고

개요

BOJ 1305 광고

• 백준 온라인 저지 1305번 문제
• BOJ 41단계

C++

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

int L;
string S;

void solve() {
    int n = S.size();
    vector<int> v(n, 0);
    int j = 0;
    for(int i=1; i<n; i++) {
        while(j>0 && S[i] != S[j]) {
            j = v[j-1];
        }
        if(S[i] == S[j]) {
            j++;
            v[i] = j;
        } else {
            v[i] = 0;
        }
    }
    cout << n - v[n-1];
}
 
int main() {
    cin >> L >> S;
    solve();
}