[c++] 백준 #11585 속타는 저녁메뉴 (190830)

< 풀이 >

KMP 문제임을 바로 이해할 수 있었고, 원형으로 계산하기 위해 기존 string을 2번 붙여줘야함을 이해했다. 문제의 출력 방식이 귀찮다. 기약분수로 나타내기 위해서 KMP 위치와 전체 N길이 사이의 최대공약수를 구해서 나눠준다. 

단, 틀렸습니다 처리를 하기 위해서는 2번 붙여준 기존 string 중 맨 마지막 글자는 빼고 KMP에 넣어줘야 문제가 발생하지 않는다.

왜냐하면, H == N인 경우 count할 때 문제가 생길 수 있기 때문이다.

 

< 소스 코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

int get_gca(int a, int b){
    while(b){
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

vector<int> getPartialMatch(const string& N){
    int m = N.size();
    vector<int> pi(m, 0);

    int begin = 1, matched = 0;
    while(begin + matched <= m){
        if (N[begin + matched] == N[matched]){
            ++matched;
            pi[begin+matched-1] = matched;
        }
        else{
            if(matched == 0) ++begin;
            else {
                begin += matched - pi[matched-1];
                matched = pi[matched-1];
            }
        }
    }
    return pi;
}

vector<int> kmpSearch(const string& H, const string& N){
    int n = H.size(), m = N.size();
    vector<int> ret;

    vector<int> pi = getPartialMatch(N);
    int begin = 0, matched = 0;
    while(begin + m <= n){
        if (matched < m && H[begin + matched] == N[matched]){
            ++matched;
            if(matched == m) ret.push_back(begin);
        }
        else {
            if (matched == 0)
                ++begin;
            else {
                begin += matched - pi[matched-1];
                matched = pi[matched-1];
            }
        }
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    string H = "";
    string N = "";
    for(int i=0; i<n;i++){
        char t; cin >> t; H += t;
    }
    for(int i=0; i<n;i++){
        char t; cin >> t; N += t;
    }
    H += H;
    //H가 N을 부분으로 가지고 있는 인덱스를 구한다(kmp로)
    vector<int> ret = kmpSearch(H.substr(0,2*n-1), N);
    int bunja = ret.size();
    int bunmo = n;

    int gca = get_gca(bunja,bunmo);
    if (gca > 1){
        bunja /= gca;
        bunmo /= gca;
    }
    cout << bunja << "/" << bunmo << '\n';
    return 0;
}