백준 17228번: 아름다운 만영로

Seungil Kim·2022년 6월 6일
0

PS

목록 보기
201/206

아름다운 만영로

백준 17228번: 아름다운 만영로

아이디어

dfs로 탐색하면서 현재 해쉬값을 가지고 간다. 맨 처음에 계산한 P랑 일치하면 정답 개수 증가. 지금까지 거쳐간 알파벳들을 벡터에 push, 롤링해쉬 계산. 함수 호출 끝나면 pop.

코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll MOD = 1e9+7;
const ll BASE = 31;
const int MAX = 500005;

ll power[MAX];
ll H;
int N, ANS;
string P;
vector<vector<pair<int, char>>> v;
vector<char> vc;

void dfs(int cur, ll hash) {
    if (hash == H) ANS++;
    for (auto p : v[cur]) {
        int nxt = p.first;
        char c = p.second;
        vc.push_back(c);
        ll h = hash;
        if (vc.size() >= P.size()) {
            h = h - vc[vc.size()-1-P.size()]*power[P.size()-1]%MOD + MOD;
        }
        h = (h*BASE + vc[vc.size()-1])%MOD;
        dfs(nxt, h);
        vc.pop_back();
    }
}

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

    cin >> N;
    v.resize(N+1);
    for (int i = 0; i < N-1; i++) {
        int a, b;
        char c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
    }
    cin >> P;

    power[0] = 1;
    for (int i = 1; i <= N; i++) {
        power[i] = power[i-1]*BASE%MOD;
    }
    for (int i = 0; i < P.size(); i++) {
        H = (H*BASE + P[i])%MOD;
    }
    
    dfs(1, 0);
    cout << ANS;

    return 0;
}

여담

해쉬 충돌하면 그때 두개 써서 해보는걸로.

profile
블로그 옮겼어용 https://ks1ksi.io/

0개의 댓글