[BOJ/C++] 14425 문자열 집합

입력받은 문자열이 집합안에 존재하는지 여부를 확인하는 문제로 set과 트라이를 이용해서 문제를 해결할 수 있습니다.

set을 이용한 방법과 트라이를 이용한 방법 2가지로 문제를 해결해보겠습니다.

해당 문제는 문자열의 부분 탐색이 아니기 때문에 해시 구조를 가지고 있는 unordered_set이 트라이보다 시간 복잡도, 공간 복잡도 면에서 좋습니다.

다만 문자열의 부분이 포함되어있는지 탐색하기 위해선 string의 find는 보이어-무어 알고리즘으로 시간 복잡도가 $O(n*m)$으로 라빈카프나 kmp 알고리즘 $O(n+m)$을 이용하는 것이 좋습니다.

1. Set을 이용한 방법

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    unordered_set<string> s;

    for(int i=0; i<N; i++)
    {
        string input;
        cin >> input;

        s.insert(input);
    }

    int result = 0;
    for(int i=0; i<M; i++)
    {
        string input;
        cin >> input;

        if (s.find(input) != s.end())
            result++;
    }

    cout << result;

    return 0;
}

2. Trie를 이용한 방법

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;


class Node
{
public:
    Node* next[26]{};
    bool isEnd = false;
    Node()
    {
        fill(next, next + 26, nullptr);
    }

    ~Node()
    {
        for(auto& child : next)
        {
            delete child;
        }
    }

    // 문자열 삽입 함수
    void insert(const char* key)
    {
        if (*key == 0)
            isEnd = true;
        else
        {
            int next_idx = *key - 'a';

            if (next[next_idx] == nullptr)
                next[next_idx] = new Node();

            next[next_idx]->insert(key + 1);
        }
    }

    // 문자열 찾기 함수
    Node* find(const char* key)
    {
        if (*key == 0)
            return this;

        int next_idx = *key - 'a';

        if (next[next_idx] == nullptr)
            return nullptr;

        return next[next_idx]->find(key + 1);
    }
};


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    Node* node = new Node();

    for(int i=0; i<N; i++)
    {
        char input[501];
        cin >> input;

        node->insert(input);
    }

    int result = 0;

    for(int i=0; i<M; i++)
    {
        char input[501];
        cin >> input;

        Node* text = node->find(input);

        if (text && text->isEnd)
            result++;
    }

    cout << result;

    
    return 0;
}