[백준 14426] 접두사 찾기

 

트라이로 구현하면 된다.

일단 모든 문자열을 트라이에 넣고 

검색할 문자열을 트라이 내에서 한 글자씩 따라가되 

만약 다음 글자노드의 주소가 null이면 해당 접두사는 없다는 뜻이므로 해당 문자열 탐색을 종료한다.

 

---

#include <iostream>
#include <string>

using namespace std;

typedef struct _Node {
	struct _Node* childs[26] = { NULL, };
	bool isWord = false;
}Node;

void insert(Node* root, string s) {
	Node* cur = root;

	for (int i = 0; i < s.size(); i++) {
		int idx = s[i] - 'a';

		if (cur->childs[idx] == NULL) {
			cur->childs[idx] = new Node;
		}
		cur = cur->childs[idx];
	}

	cur->isWord = true;
}

bool checkprefix(Node* root, string target) {
	Node* cur = root;

	for (int i = 0; i < target.size(); i++) {
		if (cur->childs[target[i] - 'a'] == NULL) {
			return false;
		}
		cur = cur->childs[target[i] - 'a'];
	}
	return true;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, M; cin >> N >> M;
	string s;

	Node* root = new Node;

	for (int i = 0; i < N; i++) {
		cin >> s;
		insert(root, s);
	}

	int cnt = 0;
	for (int i = 0; i < M; i++) {
		cin >> s;
		if (checkprefix(root, s)) cnt++;
	}

	cout << cnt;
	return 0;
}