www.acmicpc.net/problem/1305

 

1305번: 광고

첫째 줄에 광고판의 크기 L이 주어지고, 둘째 줄에 현재 광고판에 보이는 문자열이 주어진다. L은 백만보다 작거나 같은 자연수이다.

www.acmicpc.net

 

위 문제는 길이가 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]을 구하면 답을 구할 수 있다.

 

 

소스코드

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

  1. #include<iostream>
  2. #include<string>
  3. #include<vector>
  4. using namespace std;
  5.  
  6. vector<int> get_pi_array(string s){
  7. int n = s.size();
  8. vector<int>pi(n);
  9. pi[0] = 0;
  10. int j = 0;
  11. for(int i=1; i < n; i++){
  12. while(j>0 && s[i] != s[j]){
  13. j = pi[j-1];
  14. }
  15. if(s[i] == s[j]){
  16. pi[i] = j + 1;
  17. j += 1;
  18. } else {
  19. pi[i] = 0;
  20. }
  21. }
  22. return pi;
  23. }
  24.  
  25. int main(){
  26. int n;
  27. string s;
  28. cin >> n >> s;
  29. vector<int> pi = get_pi_array(s);
  30. cout << n - pi[n-1] << '\n';
  31. return 0;
  32. }

 

 

관련 사이트:

bowbowbow.tistory.com/6

m.blog.naver.com/kks227/220917078260

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24
BOJ 10826 피보나치 수 4  (0) 2020.09.04
1516 게임 개발  (0) 2020.09.04
BOJ 2407 조합  (0) 2020.09.04

+ Recent posts