문제 출처

1. 문제설명

  • 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 문자열 중 적어도 하나의 접두사인 것의 개수

  • 문제 분류

    • Data Structure, String, Tree, Binary Search, Trie


2. 알고리즘 설계

  • Trie 문제이다.
  • Trie의 insert를 이용해 M개의 문자를 넣고 find를 통해 찾을 수 있다면 정답 + 1을 해주면 된다.
    • 만약 다음 글자를 탐색하는 과정에서 다음 글자 정보를 담은 nxt 배열의 값이 -1이라면 return false
    • 탐색 끝까지 문제가 없었다면 return true


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 true;
}

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;
}