[C++ 백준 풀이] 3356번 : 라디오 전송 / 3779번 : 주기 (KMP 응용)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 3356번 : '라디오 전송', 3779번 : '주기' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Platinum 티어에 해당하며, 문제를 풀이하기 위해 문자열 탐색 알고리즘인 KMP 알고리즘에 대한 이해가 필요합니다.

 

 

3356번 : 라디오 전송

 

반복되어 나오는 문자열이 주어졌을 때, 가능한 가장 짧은 부분 문자열의 길이를 출력하는 문제입니다.

문자열이 반복되어 나온다는 점에서 이전에 풀이한 1305번 : '광고' 문제와 똑같습니다.

 

 

[C++ 백준 풀이] 16900번 : 이름 정하기 / 1305번 : 광고 / 1498번 : 주기문 (KMP 응용)

 

풀이 역시 위 포스트의 1305번 : '광고' 문제와 풀이와 코드가 완전히 동일합니다.

따라서 위 포스트에 정리되어 있는 1305번 : '광고' 문제의 풀이를 참고해주세요.

 

 

 

 

3779번 : 주기

 

문자열 S의 모든 접두사에 대해 주기문인지를 조사하고, 반복 문자열의 길이가 2 이상인 주기문인 경우 주기문의 길이와 반복 횟수를 출력하는 문제입니다.

 

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> GetPi(string &Pattern) {
    vector<int> Pi(Pattern.length());
    for(int i=1, j=0; i<Pattern.length(); i++) {
        while(j>0 && Pattern[i] != Pattern[j]) j = Pi[j-1];
        if(Pattern[i] == Pattern[j]) Pi[i] = ++j;
    }
    return Pi;
}

int main() {
    for(int t=1; ; t++) {
        int N;
        cin >> N;
        if(N == 0) break;
        string Str;
        cin >> Str;
        vector<int> Pi = GetPi(Str);
        int L = Str.length();
        printf("Test case #%d\n", t);
        for(int i=1; i<=L; i++)
            if(i%(i-Pi[i-1]) == 0 && i/(i-Pi[i-1]) > 1)
                printf("%d %d\n", i, i/(i-Pi[i-1]));
        printf("\n");
    }
}

 

풀이는 위와 같으며, 문자열의 길이와 Pi 배열 값의 관계식을 이용하여 주기문의 길이와 반복 횟수를 찾을 수 있습니다.

 

[C++ 백준 풀이] 1893번 : 시저 암호 / 4354번 : 문자열 제곱 (KMP)

 

해당 유형의 문제에 대한 그림 설명은 위의 링크에 첨부되어 있으니 참고하시면 유용할 것입니다.