hihoCoder#1014 : Trie树

墨蓝 2022-08-21 00:06 117阅读 0赞

简单的Trie树练习

#include<iostream>  
    #include<cstdio>  
    #include<cstdlib>  
    #include<cstring>  
    #include<string>  
    #include<queue>  
    #include<algorithm>  
    #include<map>  
    #include<iomanip> 
    #include<vector>
    using namespace std;
    struct node
    {
    	char ch;
    	int num=0;
    	vector<node*>son;
    };
    node root[26];
    void build()
    {
    	string word;
    	cin >> word;
    	node * p=NULL;
    	for (int i = 0; i < 26; i++)
    	{
    		if (word[0] == root[i].ch)
    		{
    			root[i].num++;
    			p = &root[i];
    			break;
    		}
    	}
    	for (int i = 1; i < word.length(); i++)
    	{
    		bool find = false;
    		for (int j = 0; j < p->son.size(); j++)
    		{
    			if (word[i] == p->son[j]->ch)
    			{
    				find = true;
    				p->son[j]->num++;
    				p = p->son[j];
    				break;
    			}
    		}
    		if (find == false)
    		{
    			node * newnode = new node;
    			p->son.push_back(newnode);
    			newnode->ch = word[i];
    			newnode->num++;
    			p = newnode;
    		}
    	}
    }
    void search()
    {
    	string word;
    	cin >> word;
    	node * p=NULL;
    	for (int i = 0; i < 26; i++)
    	{
    		if (word[0] == root[i].ch)
    		{
    			if (root[i].num != 0)
    				p = &root[i];
    			break;
    		}
    	}
    	if (p == NULL)
    	{
    		cout << 0 << endl;
    		return;
    	}
    	for (int i = 1; i < word.length(); i++)
    	{
    		bool find = false; 
    		for (int j = 0; j < p->son.size();j++)
    		{
    			if (word[i]==p->son[j]->ch)
    			{
    				find = true;
    				p = p->son[j];
    				break;
    			}
    		}
    		if (find == false)
    		{
    			cout << 0 << endl;
    			return;
    		}
    		if (i == word.length() - 1)
    		{
    			cout << p->num << endl;
    			return;
    		}
    	}
    	cout << p->num << endl;
    	return;
    }
    int main()
    {
    	int character = 97;
    	for (int i = 0; i < 26; i++)
    	{
    		root[i].ch = (char)character;
    		character++;
    	}
    	int n, m;
    	cin >> n;
    	for (int i = 0; i < n; i++)
    		build();
    	cin >> m;
    	for (int i = 0; i < m; i++)
    		search();
    	system("pause");
    	return 0;
    }