[백준 14426번] 접두사 찾기

문제 링크: https://www.acmicpc.net/problem/14426

14426번: 접두사 찾기

<문제 풀이> 트라이(Trie)

 

트라이를 사용해서 문자열 삽입, 검색

 

<C++소스코드>

 

#include<iostream>
#include<string>
#include<cstring>
using namespace std;

class Trie {
public:
	static const int MX = 10000 * 500;
	static const int ROOT = 1;
	int unused = 2;
	int nxt[MX + 1][26];
	Trie() {
		memset(nxt, 0xff, sizeof(nxt));
	}

	void insert(const string& s) {
		int cur = ROOT;
		for (auto& c : s) {
			if (nxt[cur][c - 'a'] == -1) nxt[cur][c - 'a'] = unused++;
			cur = nxt[cur][c - 'a'];
		}
	}
	bool find(const string& s) {
		int cur = ROOT;
		for (auto& c : s) {
			if (nxt[cur][c - 'a'] == -1) return false;
			cur = nxt[cur][c - 'a'];
		}
		return true;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	Trie* trie = new Trie();
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s; cin >> s;
		trie->insert(s);
	}
	int ans = 0;
	for (int i = 0; i < m; i++) {
		string s; cin >> s;
		ans += trie->find(s);
	}
	cout << ans;
	return 0;
}