[C++] 11585번 속타는 저녁 메뉴 (추후 보강 예정)

 

 

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

---

 

25/10/04

 

 

문제의 의도는 너무 뻔하다. KMP로 풀라는 문제인데, 일단 나는 라빈-카프로 문제를 해결했고, 사실 KMP든 라빈-카프든 둘 다 필요 없는 허점이 많은 문제이다.

---

 

문제 접근 방식:

 

 

아이디어는 간단하다. 기존 문자열을 2배한 문자열을, 매칭시키고 싶은 패턴 문자열과 매칭시켜서 몇번 매칭되는 지 확인하면 된다.

 

기존 문자열을 2배한 문자열의 길이는 최대 200만이고, 매칭시키고 싶은 패턴 문자열의 길이는 100만이기 때문에, 일반적인 나이브한 접근을 한다면 $\mathcal{O}(NM)$의 시간복잡도로 인해 터진다.

 

따라서 이걸 빠르게 하기 위해 KMP를 쓰는데...

 

일단 나는 KMP를 명확하게 이해하지 못했기 때문에 해싱을 사용해서 문제를 해결했다.

 

모듈로값은 $2 \ 147 \ 483 \ 659$로 잡았고, Base값은 $2$로 잡았다.

 

 

롤링 해시를 이용하면 다음 해시값을 다음과 같은 공식으로 구할 수 있다.

 

$$H[\text{next}] = H[\text{now}] \cdot \text{(base)} - P[i-m]\cdot (\text{base})^{m} + P[i]$$

 

이를 이용하여 해시값을 $\mathcal{O}(1)$에 구하고 해시값끼리 비교하면 된다.

 

 

근데 사실 그럴 필요도 없는게, 룰렛의 반복 단위가 있으면, 룰렛의 2배를 한 문자열에서 룰렛을 찾으려고 할 때, 처음으로 찾을 수 있는 인덱스가 몇번 반복 되었는지의 횟수이기 때문이다.

 

예를 들어 AABAAB라면, AABAAB를 2배로 한 문자열 AABAABAABAAB에서 0번째를 제외한 곳에서 AABAAB를 처음으로 찾을 수 있는 곳은 3번째 인덱스이며, 실제로 3번 반복된다.

 

따라서 Python으로 구현하면 쉽게 100바이트 이내에 구현할 수 있다.(시간초과는 나지 않는다.)

 

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 11585번 속타는 저녁 메뉴
// 라빈 카프
#include <iostream>
#include <vector>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

const long long MOD = 2147483659LL;

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

int main(void){
    fastio

    int N; cin >> N;
    vector<char> roulette(2*N-1);
    long long target = 0;
    char c;
    int ans = 0;
    for (int i = 0; i < N; ++i){
        cin >> c;
        target = ((((target << 1) % MOD) + (long long) c)) % MOD;
    }
    long long T = 1;
    for (int i = 0; i < N; ++i){
        cin >> roulette[i];
        if (i != N-1){
            roulette[i+N] = roulette[i];
        }
        T = (T << 1) % MOD;
    }
    long long hash_val = 0;
    for (int i = 0; i < N; ++i){
        hash_val = ((((hash_val << 1) % MOD) + (long long) roulette[i])) % MOD;
    }
    if (hash_val == target){
        ans++;
    }
    for (int i = N; i < 2*N-1; ++i){
        if (((hash_val << 1) % MOD) < ((roulette[i-N] * T) % MOD)){
            hash_val = ((hash_val << 1) % MOD) - ((roulette[i-N] * T) % MOD) + MOD;
        } else {
            hash_val = ((hash_val << 1) % MOD) - ((roulette[i-N] * T) % MOD);
        }
        hash_val = (hash_val + roulette[i]) % MOD;
        if (hash_val == target){
            ans++;
        }
    }
    int G = gcd(N, ans);
    cout << ans/G << '/' << N/G << endl;
    return 0;
}