백준 5052 접두사 찾기 c++ // 트라이, 접두사검사, 포함검사

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

 

1. 트라이

해당 문자 삽입, 삭제, 검색을 O( s.size()) 만에 가능하게 하는 알고리즘이다.

주로 접두사검사, 포함검사, 자동완성기능 키워드가 있으면, 트라이 문제이다!

1. 삽입

2. 삭제

chk[cur] 만 0으로 만들어 놓으면된다.

3. 검색

자식이 -1이면, false를 반환하면된다.

그외에는 1 반환. -> 접두사검사

chk[cur] 반환 -> 완전한 포함검사

 

 

2. 전체코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int ROOT = 1; //1번부터 시작!
int unused = 2; //다음노드 넣을 번호
const int MX = 10000 * 500 + 5; // N * 문자열길이 : 최대 등장 가능한 글자의 수
bool chk[MX]; // 해당노드가 단어의 끝인지
int nxt[MX][26]; 
//[노드][자식'A'] = 자식번호
//[1]['A'] = 2 //1번노드의 자식이 A이고, 그 번호가 2번임
//[1]['B'] = -1(초기값) : B라는 자식이 없음

int c2i(char c) {
    return c - 'a';
}

void insert(string& s) {
    int cur = ROOT;
    for (auto c : s) {
        if (nxt[cur][c2i(c)] == -1) //기존에 없던 문자면
            nxt[cur][c2i(c)] = unused++; //번호부여, unused갱신(2->3)
        cur = nxt[cur][c2i(c)]; // 새 노드(2) 가르키도록
    }
    chk[cur] = true; //단어의 끝 표시
}

bool find(string& s) {
    int cur = ROOT;
    for (auto c : s) {
        if (nxt[cur][c2i(c)] == -1)
            return false;
        cur = nxt[cur][c2i(c)];
    }
    //return chk[cur]; //딱맞는 단어 검사
    return true; //접두사검사
}

void erase(string& s) {
    int cur = ROOT;
    for (auto c : s) {
        if (nxt[cur][c2i(c)] == -1)
            continue;
        cur = nxt[cur][c2i(c)];
    }
    chk[cur] = 0; //단어의 끝 표시만 지우면 됨.
}
int n, m;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < MX; i++)
        fill(nxt[i], nxt[i] + 26, -1);

    cin >> n >> m;
    while (n--) {
        string s;
        cin >> s;
        insert(s);
    }

    int ans = 0;
    while (m--) {
        string s;
        cin >> s;
        ans += find(s);
        //if (find(s)) cout <<"정답:"<< s << "\n";
    }
    cout << ans;
}