백준(BOJ) 11585 속타는 저녁 메뉴

내 속도 탄다. 이런 젠장

 

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

KMP 알고리즘을 사용하면 된다. 룰렛을 돌릴 문자열을 한번 더 더하면, 즉 원래 문자열이 S라면 S + S라고 하면 룰렛을 돌린 효과를 얻을 수 있다.
S + S에 대해 KMP 알고리즘을 적용하면 문제가 쉽게 풀린다.
단, S + S의 마지막을 POP 해줘야 한다. 안그러면 (예를 들어) ABC 라는 문자열이 들어왔을 때 ABCABC가 되어서
상근이가 고기를 먹을려면 나와야하는 ABC를 두 번이나 세게 된다.
그러니까 처음 상태에서 룰렛을 계속 돌리면 다시 처음 상태로 돌아올 텐데, 이 돌아온 상태까지 센다는 말이다.

/* 속타는 저녁 메뉴 */

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

int Denominator, Numerator, N;

string Meat, Circle;
vector<int> Meat_get;

void get_meat();
void kmp();
void prime_factor();

int main(void) {
    scanf("%d ", &N);
    Denominator = N;

    Meat.resize(N); Circle.resize(N);
    for (int i = 0; i < N; i++) 
        scanf(" %c", &Meat[i]);

    for (int i = 0; i < N; i++) 
        scanf(" %c", &Circle[i]);

    Circle += Circle; Circle.pop_back();
    get_meat();
    kmp();
    if (Numerator == Denominator + 1) {
        cout << "1/1";
        return 0;
    }

    prime_factor();
    return 0;
}

void get_meat() {
    Meat_get.resize(N);
    for (int i = 1, j = 0; i < N; i++) {
        while (j > 0 && Meat[i] != Meat[j])
            j = Meat_get[j - 1];
        if (Meat[i] == Meat[j])
            Meat_get[i] = ++j;
    }
}

void kmp() {
    for (int i = 0, j = 0; i < (int)Circle.size(); i++) {
        while (j > 0 && Meat[j] != Circle[i])
            j = Meat_get[j - 1];
        if (Meat[j] == Circle[i]) {
            if (j == N - 1) {
                Numerator++;
                j = Meat_get[j];
            }
            else
                j++;
        }
    }
}

void prime_factor() {

    int a = Numerator, b = Denominator;
    while (a != 0)
    {
        int t = b % a;
        b = a;
        a = t;
    }
    printf("%d/%d\n", Numerator / b, Denominator / b);
}