[C++] 1305번 광고 - KMP, 문자열

1. 문제

• 전광판의 크기는 전광판에서 한 번에 보이는 최대 문자수를 나타낸다. 광고업자는 길이가 N인 광고를 무한이 붙여서 광고한다. 세준이가 어느 순간 전광판을 쳐다봤을 때, 그때 쓰여 있는 문자가 입력으로 주어졌을 때, 가능한 광고의 길이중 가장 짧은 것을 출력하는 프로그램을 작성하시오.

<입력>

• - 1 -   광고판 크기 \(L(1 \leq L \leq 1,000,000)\)
• - 2 -   현재 광고판에 보이는 문자열

<출력>

• - 1 -   가능한 광고의 길이 중 가장 짧은 것의 길이

2. 재정의

• 문자열이 주어졌을 때 최소 반복 주기를 구하여라.

3. 해결 방법

• KMP failure function을 구한다.
• L - failure function[last index]가 가능한 광고의 길이중 가장 짧은 것.(정당성 증명은 생략)

4. 실수한 점, 개선할 점

• X

 

<코드>

#include <iostream>

using namespace std;

const int MAX_L = 1000001;

// <문제>
// 광고판 크기 L
int L;
// 현재 광고판에 보이는 문자열
char s[MAX_L];

// KMP 알고리즘
int pi[MAX_L];

void input() {
    cin >> L;
    cin >> s;
}

// KMP 알고리즘 failure function 얻기
void getPi() {
    int j=0;
    for(int i=1; i<L; i++) {
        while(j>0 && s[i] != s[j])
            j = pi[j-1];
        if(s[i] == s[j])
            pi[i] = ++j;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    getPi();
    
    cout << L - pi[L-1];
    
    return 0;
}

 

<KMP 알고리즘>

https://bowbowbow.tistory.com/6

KMP : 문자열 검색 알고리즘

 

<문제 바로가기>

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

1305번: 광고

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.