글 읽기 - Trie 시간초과?

qotmd01 1년 전 0

일반적인 트라이 자료구조 코드와 다를바가 없다고 생각하는데, 왜 이 문제에서 이 코드가 시간초과를 유발하는지 모르겠습니다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Node{
    int child[26];
    Node(){
        for (int i = 0; i < 26; ++i) {
            child[i] = -1;
        }
    }
};

int root;
vector<Node> trie;

int init(){
    Node new_node = Node();
    trie.push_back(new_node);
    return trie.size() - 1;
}

void add(int cur_node, string s, int idx){
    if (idx == s.length()) return;
    int cur_c = s[idx] - 'a';
    if (trie[cur_node].child[cur_c] == -1){
        int nxt = init();
        trie[cur_node].child[cur_c] = nxt;
    }
    add(trie[cur_node].child[cur_c], s, idx + 1);
}

bool search(int cur_node, string s, int idx){
    if (cur_node == -1) return false;
    if (idx == s.length()) return true;
    int cur_c = s[idx] - 'a';
    return search(trie[cur_node].child[cur_c], s, idx + 1);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m,ans = 0;
    cin >> n >> m;
    root = init();
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        add(root, s, 0);
    }
    for (int i = 0; i < m; ++i) {
        string s;
        cin >> s;
        if (search(root, s, 0)) ans++;
    }
    cout << ans << "\n";
}

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

문제

문제

출처

ICPC

Trie 시간초과?

qotmd01 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말