BOJ)14426 접두사 찾기

문제: icpc.me/14426

N개의 문자열로 이루어진 집합 S가 주어질 때 M개의 문자열 중에서 집합 S에 포함 된 문자열 중 하나 이상의 접두사인 문자열들의 수를 출력하는 문제이다.

문자열의 길이가 짧음을 이용하여 트라이를 사용하여 문제를 해결 할 수 있다.

 N개의 문자열을 모두 트라이에 삽입해준 뒤 문자열 X에 대해 검색을 한다고 가정하면 X가 끝날 때 까지 트라이에서 계속 탐색이 가능하면 true를 중간에 경로가 없다면 false 를 return하도록 구현해주면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m;
char s[555];
struct trie {
    trie* go[26];
    trie() {
        for (int i = 0; i < 26; i++)
            go[i] = 0;
    }
    ~trie() {
        for (int i = 0; i < 26; i++)
            if (go[i])delete go[i];
    }
    void insert(const char *key) {
        if (*key == '\0')return;
        int here = *key - 'a';
        if (!go[here])
            go[here] = new trie;
        go[here]->insert(key + 1);
    }
    bool query(const char *key) {
        if (*key == '\0')return true;
        int here = *key - 'a';
        if (!go[here])return false;
        return go[here]->query(key + 1);
    }
};
int main() {
    trie root;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%s", &s);
        root.insert(s);
    }
    int res = 0;
    for (int i = 0; i < m; i++) {
        scanf("%s", &s);
        res += root.query(s);
    }
    printf("%d\n", res);
    return 0;
}