Hdu 1247 Hat’s Words (Trie动态写法+STL) + UVa 11732 strcmp() Anyone (Trie的另一种建立方法)

超、凢脫俗 2023-06-01 12:49 8阅读 0赞

**Hdu 1247 Hat’s Words**

题意：按字典序给出一些单词， 寻找其中哪些单词是由其他两个单词（可以是同一个用两次）拼接而成。按字典序输出。

思路：将所有单词插入Trie树。枚举拆分每个单词。

#include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    
    struct Trie
    {
    	Trie *next[26];
    	bool flag;
    	Trie ()
    	{
    		flag=false;
    		for (int i=0;i<26;i++)
    			next[i]=NULL;
    	}
    	~Trie ()
    	{
    		for (int i=0;i<26;i++)
    			if (next[i] != NULL)
    				delete next[i];
    	}
    };
    Trie *root=NULL;
    char data[50005][30],str[30];
    
    void Insert (char str[])
    {
    	Trie *p=root;
    	if (p==NULL)
    	{
    		root=new Trie();
    		p=root;
    	}
    	int i=0;
    	while (str[i])
    	{
    		if (p->next[str[i]-'a']==NULL)
    			p->next[str[i]-'a']=new Trie();
    		p=p->next[str[i++]-'a'];
    	}
    	p->flag=true;
    }
    
    bool Find (char str1[])
    {
    	Trie *p=root;
    	if (p==NULL)
    		return false;
    	int i=0;
    	while (str1[i])
    	{
    		if (p->next[str1[i]-'a']==NULL)
    			return false;
    		p=p->next[str1[i++]-'a'];
    	}
    	if (p->flag)
    		return true;
    	return false;
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int id=0;
    	while (~scanf("%s",data[id]))
    		Insert(data[id++]);
    	for (int i=0;i<id;i++)
    	{
    		bool flag=false;
    		int len=strlen(data[i]);
    		for (int j=0;j<len-1;j++) //注意单词的分割位置
    		{
    			for (int k=0;k<=j;k++)
                    str[k]=data[i][k];
    			str[k]=0;
    			if (Find(str))
    			{
    				strcpy(str,data[i]+k);
    				if (Find(str))
    				{
    					puts(data[i]);
    					break;
    				}
    			}
    		}
    	}
    	delete root;
    	return 0;
    }

用STL比较简洁，用时不到300ms。

#pragma warning(disable:4786)
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <map>
    #include <iostream>
    using namespace std;
    
    string data[50500];
    
    int main()
    {
    	map<string,int> m;
    	int num=-1;
    	while (cin>>data[++num])
    		m[data[num]]=1;
    	map<string,int> ::iterator p;
    	for (p=m.begin();p!=m.end();p++)
    	{
    		string t;
    		t=p->first;
    		if (t.length()==1)
    			continue ;
    		for (int i=1;i<t.length();i++)
    		{
    			string str1(t,0,i);
    			string str2=&t[i];
    			if (m[str1]!=0 && m[str2]!=0)
    			{
    				for (int j=0;j<m[t];j++)
    					cout<<t<<endl;
    				break;
    			}
    		}
    	}
    	return 0;
    }

**UVa 11732 strcmp() Anyone**

很好的一题，只可惜自己没做出来……这个题空间需求量很大，经典建树方法会爆内存，可以用一种特殊的建树方法，详见：

http://blog.csdn.net/c3568/article/details/8591521

http://oibh.info/archives/147