직접 만들어 본 트라이 (문제점: 메모리를 주구장창 먹음)

trie.cpp

#include<iostream>
#include<vector>
using namespace std;

//트라이  (trie)
struct TrieNode
{
	TrieNode* child[256];
	int contains[256]={0};
	int childcnt=0;
	bool isLeaf=false;
	int value;
	TrieNode()
	{
		for(int i=0;i<256;i++)child[i]=nullptr;
	}
	void Insert(string s, int val)
	{
		TrieNode* cur=this;
		for(char c:s)
		{
			if(cur->contains[c]==0)cur->child[c] = new TrieNode;
			cur->contains[c]++;
			cur->childcnt++;
			cur=cur->child[c];
		}
		cur->isLeaf=true;
		cur->value=val;
	}
	int Search(string s)
	{
		TrieNode* cur=this;
		for(char c:s)
		{
			if(!cur->contains[c])return -1;
			cur=cur->child[c];
		}
		return cur->value;
	}
	void Delete(string s)
	{
		vector<TrieNode*> vec;
		vec.push_back(this);
		for(char c:s)
		{
			if(!vec.back()->contains[c])return;
			vec.push_back(vec.back()->child[c]);
		}
		vec.pop_back();
		for(int i=vec.size()-1;i>=0;i--)
		{
			vec[i]->childcnt--;
			vec[i]->contains[s[i+1]]--;
			if(vec[i]->contains[s[i+1]]==0)delete vec[i]->child[s[i+1]];
		}
	}
};

int main()
{
	TrieNode Trie;
	int n,m;
	cin>>n>>m;
	while(n--)
	{
		string s;cin>>s;
		Trie.Insert(s,1);
	}
	int ans=0;
	while(m--)
	{
		string s;cin>>s;
		if(Trie.Search(s)==1)ans++;
	}
	cout<<ans;
}