문제 출처

1. 문제설명

  • M개, S개의 문자열 집합이 주어진다.

  • M개의 문자열 중에 총 몇개가 집합 S에 포함되는지?

  • 문제 분류
    • Data Structure, String, set and map using hash, set and map using tree


2. 알고리즘 설계

  • Trie 문제이다.
    • 한글자씩 트리구조에 넣어준다.
    • 만약 이동 중에 글자가 없다면 자식 노드를 추가해준다.
    • 장단점
      • 문자열 검색 시 하나씩 비교하는 것보다 시간복잡도 측면에서 빠름.
      • 자식들에 대한 포인터를 전부 배열로 저장하기 때문에 공간의 크기가 큼.
  • Trie의 insert를 이용해 M개의 문자를 넣고 find를 통해 찾을 수 있다면 정답 + 1을 해주면 된다.


3. 전체 코드

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

int n, m;
const int ROOT = 1;
int unused = 2;
const int MX = 10'000 * 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 main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int ans = 0;

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

	for(string s; n--;) {
		cin >> s;
		insert(s);
	}
	for(string s; m--;) {
		cin >> s;
		ans += find(s);
	}

	cout << ans;

	return 0;
}