[C++] 백준 14425번: 문자열 집함

문제링크

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

풀이방법

해당 문제를 트라이 알고리즘을 공부하기 위한 목적으로 트라이 알고리즘을 이용하여 풀었다. 트라이 알고리즘이란 문자열을 효율적으로 처리하기 위한 트리 자료 구조이다.

트라이 알고리즘에 대해서 잘 몰라서 공부가 필요하면 아래 영상을 참고하자 문제에 대한 상세 풀이도 존재한다.

https://www.youtube.com/watch?v=ZmLe4tc5XRI&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=32

코드

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

const int ROOT = 1;
int unused = 2;
const int MX = 10000 * 500 + 5; // 최대 등장 가능한 글자의 수
bool chk[MX];
int nxt[MX][26];

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++;
    cur = nxt[cur][c2i(c)];
  }
  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];
}

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);
  }
  cout << ans;
}