백준 1305번: 광고 (C++)

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

1305번: 광고

---

Solved By: KMP

 

주어진 광고에서 앞(접두사)과 뒤(접미사)가 얼마나 중복되는지 길이를 안다면 전체 길이에서 그 길이를 빼서 얼마큼만 광고해도 되는지 구할 수 있다.

 

이때 문자열 알고리즘 KMP를 사용한다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(){
    int l; string s;
    cin >> l >> s;
    vector<int> pattern(l + 1);
    for(int i = 1, j = 0; i < l; i++){
        while(j > 0 && s[i] != s[j]){
            j = pattern[j - 1];
        }
        
        if(s[j] == s[i]){
            pattern[i] = ++j;
        }
    }
    
    cout << l - pattern[l - 1];
    return 0;
}