BOJ 1305 광고

www.acmicpc.net/problem/1305

1305번: 광고

 

위 문제는 길이가 N 인 광고판에 문자열 길이가 L 인 광고가 왼쪽 쉬프트를 하며 무한히 나타날 때, 가능한 문자열의 최소 길이를 구하는 문제이다. 즉, 광고판 길이가 6이고 현재 광고판의 문자열이 "aabaaa" 일때, 가능한 문자열 후보는 "aaba", "aaab", "abaa", "aabaa", "abaaa" 등 다양하지만, 가장 짧은 길이는 4이다.

 

이 문제는 KMP 알고리즘에서 사용하는 pi 배열을 이용하여 풀 수 있다. pi 배열은 접두사(prefix) 와 접미사(suffix)가 같은 부분 문자열 중 가장 길이가 긴 것을 저장한다.

 

"ABADABC" 라는 문자열이 있을 때, pi는 다음과 같이 저장된다.

i	부분 문자열	pi[i]
0	A	0
1	AB	0
2	ABA	1
3	ABAD	0
4	ABADA	1
5	ABADAB	2
6	ABADABC	0

 

KMP는 이 pi배열을 이용해 문자열 검색의 시간 복잡도를 O( |S| * |P| ), (S : 전체 문자열, P : 전체 문자열에서 찾고자하는 패턴(검색) 문자열) 에서 O( |S|+|P| ) 로 줄이는 알고리즘이다.

 

1305 광고문제는 검색까지는 필요없고, Pi만 배열만 있으면 풀 수 있다.

길이가 N인 광고판과 길이가 L (L <= N) 인 문자열이 있을 때, 앞의 X개의 문자열(진한 파란색)은 광고 문자열 L번째 문자 뒤에 반복된다.

 

즉, N길이의 광고판 문자열에 대해 pi 를 구한 후, N-pi[N]을 구하면 답을 구할 수 있다.

 

 

소스코드

소스는 백준님 풀이 방식을 기반으로 구현했습니다.

#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
vector<int> get_pi_array(string s){
    int n = s.size();
    vector<int>pi(n);
    pi[0] = 0;
    int j = 0;
    for(int i=1; i < n; i++){
        while(j>0 && s[i] != s[j]){
            j = pi[j-1];
        }
        if(s[i] == s[j]){
            pi[i] = j + 1;
            j += 1;
        } else {
            pi[i] = 0;
        }
    }
    return pi;
}
 
int main(){
    int n;
    string s;
    cin >> n >> s;
    vector<int> pi = get_pi_array(s);
    cout << n - pi[n-1] << '\n';
    return 0;
}

 

 

관련 사이트:

bowbowbow.tistory.com/6

m.blog.naver.com/kks227/220917078260