Algorithm/problem

백준 11585번 : 속타는 저녁 메뉴 - kmp

DingCoDing 2022. 11. 28. 01:27
반응형

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

 

11585번: 속타는 저녁 메뉴

수원이와 친구들은 저녁 메뉴를 잘 선택하지 못한다. 배가 고픈 수원이가 보다 못해 메뉴를 정하곤 하는데 이마저도 반대에 부딪히는 경우에는 수원이가 원형 룰렛을 돌려 결정하곤 한다. 이 원

www.acmicpc.net

 

#include <iostream>

using namespace std;

#define MX 1'000'003

int N;
char arr1[2 * MX], arr2[MX];

int fail[MX];

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

void getFail() {
    int j = 0;
    for (int i = 1; i < N; i++) {
        while (j > 0 && arr2[i] != arr2[j]) {
            j = fail[j - 1];
        }
        if (arr2[i] == arr2[j]) {
            fail[i] = ++j;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);


    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr1[i];
        arr1[i + N] = arr1[i];
    }

    for (int i = 0; i < N; i++) {
        cin >> arr2[i];
    }


    getFail();

    int cnt = 0;
    int j = 0;
    for (int i = 0; i < 2 * N; i++) {
        while (j > 0 && arr1[i] != arr2[j]) {
            j = fail[j - 1];
        }

        if (arr1[i] == arr2[j]) {
            if (j == N - 1) {
                if (i - j < N)cnt++;

                j = fail[j];
            } else {
                j++;
            }
        }
    }

    int _gcd = gcd(N, cnt);
    cout << cnt / _gcd << '/' << N / _gcd << '\n';
}
반응형