[백준 17228] 아름다운 만영로

문제

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

 

알고리즘

라빈 카프

 

해설

정원의 쉼터가$N-1$개의 길로 연결되어있다는 점에서 트리임을 알 수 있고, 반대방향으로 이동하는 것을 금지한다는 조건에서 DFS접근방식을 생각했습니다. 만영이 취향의 문자열을 해싱한 후, DFS를 수행하며 수행과정에서 얻는 문자열 또한 해싱하며, 해시값이 동일하다면 정답을 카운트해주면 됩니다. 처음 $recur()$ 에서는 롤링 해시할 길이가 없으므로, 가짜 문자인 $를 넣어주었습니다. DFS와 라빈 카프를 이용했으므로 시간 복잡도는 $O(V+E+N)$입니다.

 

코드

#include <bits/stdc++.h>
#include <unordered_set>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

typedef long long ll;
typedef pair<int, char> pic;
const int MOD = 1000000000 + 7;
const int BASE = 31;

char x;
int N,u,v,slen,ans;
string S;
//str : DFS를 수행하며 얻은 문자열
vector<char> str;
vector<vector<pic>> adj;

// h: 만영이가 좋아하는 문자열의 해시값
// fw: 롤링해시값
// b : 롤링해시에서 사용하는 power값
ll h,fw, b;

// recur() : DFS를 수행하며 롤링해시를 하는 함수
void recur(int here) {
    fw = (fw - str[str.size() - 1 - slen] * b % MOD + MOD) % MOD;
    fw = (fw * BASE + str[str.size() - 1]) % MOD;

    if (h == fw) ++ans;

    for (auto [there, flower] : adj[here]) {
        ll temph = fw;
        str.emplace_back(flower);
        recur(there);
        str.pop_back();
        fw = temph;
    }
}

int main() {
    FAST;
    cin >> N;
    adj.resize(N);
    rep(i, N - 1) {
        cin >> u >> v >> x;
        --u, --v;
        adj[u].emplace_back(v, x);
    }
    cin >> S;
    slen = S.size();

    rep(i, slen) str.emplace_back('$');
    fw = str[0];
    h = S[0];
    b = 1;
    for (int i = 1;i < slen;++i) {
        h = (h * BASE + S[i]) % MOD, b = b * BASE % MOD;
        fw = (fw * BASE + str[i]) % MOD;
    }
    str.emplace_back('$');
    recur(0);
    cout << ans;

    return 0;
}