티스토리 뷰

알고리즘 관련/BOJ

BOJ)14426 접두사 찾기

JASON 자손9319 2017. 8. 4. 03:09

문제: icpc.me/14426


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)3172 현주와 윤주의 재미있는 단어 게임  (0) 2017.08.15
BOJ)14675 단절점과 단절선  (1) 2017.08.06
BOJ)14426 접두사 찾기  (0) 2017.08.04
BOJ)1938 통나무 옮기기  (0) 2017.08.03
BOJ)1445 일요일 아침의 데이트  (11) 2017.08.03
BOJ)10256 돌연변이  (0) 2017.08.03
TAG
댓글
댓글쓰기 폼