[Platinum 4] 1305 광고

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

 

어느 순간 전광판을 바라보았을 때의 문자열에 가능한 광고 문자열의 길이를 찾아내는 것이 핵심이다.

따라서 실제 광고의 길이가 어떤지는 중요한 점이 아니다.

입력으로 주어진 문자열에서 가능한 광고의 길이를 찾아내는 것.

 

"aabaaa" 라는 문자열에서 가능한 광고 길이 중 가장 짧은 것을 알아내 보자

광고판의 길이가 6인 점은 입력을 통해 할 수 있다.

따라서 어느 순간 광고판을 바라보았을 때의 문자열의 접미사는 곧 광고의 접두사여야 한다.

왜냐하면 광고판의 문자열은 한칸씩 옆으로 이동하기 때문이다.

 

"aabaaa"의 접미사 "aa"는 광고 "aaba"의 접두사인 "aa"가 된다.

즉, (광고 + 광고의 접미사) 형태로 전광판의 남은 부분을 광고의 접미사로 채우게 된다.

 

문제에서 요구하는 광고의 길이를 찾기 위해서는

전광판 문자열의 접두사와 접미사가 같은 최대 길이를 구하면 된다.

즉, 실패함수를 구하는 것과도 같다.

최대 길이를 구하는 이유는, 접미사는 전광판에서 광고로 채우고 남은 부분을 채우기 때문에

접미사가 길어야지만 가능한 광고의 길이가 길어진다.

 

전광판 길이에서 접두사와 접미사가 같은 최대 길이를 구하는 것이기에

1. 실패함수 테이블을 전처리로 구한 후

2. L − table[L−1] 을 답으로 도출하면 된다.

index	String	Prefix	Suffix	table[index]
0	"a"	X	X	0
1	"aa"	"a"	"a"	1
2	"aab"	X	X	0
3	"aaba"	"a"	"a"	1
4	"aabaa"	"aa"	"aa"	2
5	"aabaaa"	"aa"	"aa"	2

 

답은 6 글자 광고판 길이의 접두사와 접미사가 같은 최대 길이인 table[5] 를 광고판 길이 L 에서 빼주면 된다.

“aabaaa” 에서 접두사와 접미사가 같은 최대 길이는 “aa” 의 길이인 2 이므로 이를 6 에서 빼주면 된다.

즉, “aabaaa” 에서 가능한 광고의 제일 짧은 길이는 4 인 것이다. “aaba” !!

 

 

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>
using namespace std;

int L;
string text, pattern;
int table[1000001];

int main() {
    cin>>L;
    cin>>text;

    pattern = text;
    int idx = 0;
    for(int i = 1;i<L;i++){
        while(idx>0 && pattern[idx] != text[i])
            idx = table[idx - 1];
        if(pattern[idx] == text[i])
            table[i] = ++idx;
    }
    cout<<L - table[L-1];
}

 

 

 

 

 

출처

https://ansohxxn.github.io/boj/1305/

[백준 1305][💚5] 광고 (KMP)