[백준 1305] 광고 C++

1305번: 광고

KMP

---

15분 정도 뚫어져라 본 결과 규칙을 찾았다.

 

문자열의 마지막이 접두사와 중복된 채로 끝난다면 해당 중복 문자열의 길이만큼 광고 문자열을 감소시킬 수 있다.

 

babba 라는 문자열이 주어졌다고 가정.

접두사 table을 만들어보자

table = {0, 0, 1, 1, 2}

테이블의 마지막 값이 2이므로 해당 문자열은 마지막 2개가 중복된다고 볼 수 있다.

따라서 문자열의 길이 5에서 중복 문자열 2개를 제외한 3개가 답이 된다. -> bab

다음 광고가 중복되는 부분부터 시작할 수 있기 때문

 

babbac 라는 문자열이 주어졌다고 가정.

접두사 table을 만들면 table = {0, 0, 1, 1, 2, 0}

테이블의 마지막 값이 0이므로 해당 문자열은 다음 광고판에 접두사로 이어지지 못한다.

따라서 최대 광고 길이는 6 - 0 = 6이 된다.

 

 

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int L;
string text, pattern;
vector<int> table;
 
int main(){
    cin >> L >> text;
    pattern = text;
    table.resize(L+1, 0);
    int j = 0;
    for(int i = 1; i < L; i++){
        while(j > 0 && pattern[j] != text[i]){
            j = table[j-1];
        }
        if(pattern[j] == text[i]){
            table[i] = ++j;
        }
    }
    
    cout << L - table[L-1];
    return 0;
}