글 읽기 - 라빈카프로 풀었는데 어디에서 틀린지 잘 모르겠습니다.

leeym95 3년 전 0

길이가 1부터 m까지의 substring중에서 입력으로 주어지는 문자열의 substring이 아닌 것을 찾아서 반환하는 문제이고

라빈카프로 길이가 L( 1 <= L <= m )인 부분 문자열들의 해쉬값을 visit 배열에 저장하고

길이가 L( 1 <= L <= m )이고 처음 k개의 알파벳으로 이루어진 부분 문자열들을 dfs 돌려서 전수조사하는 방식으로

굳이(?) 해쉬를 이용하여 풀어보았는데 어디가 틀린지 잘 모르겠습니다...

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

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

const int MOD = 100003;
int visit[MOD];

int mod(int n){
    if(n >= 0) return n % MOD;
    return ((-n/MOD+1)*MOD + n) % MOD; // 음수일 경우
}
int dfs(int L, int k, int cnt, string ret, int hash) {
    if(cnt == L) {
        if(!visit[hash]) {
            cout << ret << '\n';
            return 1;
        }
        return 0;
    }

    for(int i=0; i<k; ++i)
    {
        char c = 'a' + i;
        ret.push_back(c);
        int isFinish = dfs(L, k, cnt + 1, ret, mod(3 * hash + c));
        if(isFinish) return 1;
        ret.pop_back();
    }
    return 0;
}
void solve() {
    int t; cin >> t;
    while(t--)
    {
        int n, m, k;
        cin >> n >> m >> k;
        string str; cin >> str;

        if(k == 1) {
            string s;
            for(int i=0; i<m; ++i)
            {
                s.append("a");
            }
            cout << s << '\n';
            continue;
        }

        for(int i=1; i<=m; ++i)
        {
            memset(visit, 0, sizeof(visit));
            int hash = 0, power = 1;
            for(int j=0; j<=n-i; ++j)
            {
                if(j == 0) {
                    for(int k=i-1; k>=0; --k)
                    {
                        hash = mod(hash + str[k] * power);
                        if(k > 0) power = mod(power * 3);
                    }
                } else {
                    hash = mod(3 * (hash - str[j-1] * power) + str[j+i-1]);
                }
                visit[hash] = 1;
            }
            int isFind = dfs(i, k, 0, "", 0);
            if(isFind) break;
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false); cin.tie(0);
    solve();
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

라빈카프로 풀었는데 어디에서 틀린지 잘 모르겠습니다.

leeym95 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말