字典树之统计难题 hdu1251

川长思鸟来 2022-08-10 15:55 189阅读 0赞

这一题本来打算存到一个字符串的数组里，到输入要查找的前缀后再去查找；结果去实现时发现如果要提前给的单词非常多的话每次查找都是比较慢的;交上去果断TLE....

即使用了快排，照样TLE......  不过好像可以再用二分查找优化一下，那样速度很快，应该不至于被判超时。

#include<cstdio>
    #include<string>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    
    char word[100000][12];
    int coun=0;
    
    int search_w(char *s)
    {
    	int len1=strlen(s),cal=0;
    	for(int i=0;i<coun;i++)
    	{
    		char tmp[15];
    		int len2=strlen(word[i]);
    		if(len2<len1)continue;
    		memset(tmp,0,sizeof(tmp));
    		for(int j=0;j<len1;j++)
    		tmp[j]=word[i][j];
    		if(strcmp(s,tmp)==0)cal++;
    		if(strcmp(s,tmp)<0)break;
    	}
    	return cal;
    }
    
    int cmp(const void* s1,const void* s2)  
    {  
        return strcmp((char*)s1,(char*)s2);  
    }  
    
    void scanword()
    {
    	while(gets(word[coun])&&word[coun][0]!='\0')
    	coun++;
    }
    int main()
    {
    	scanword();
    	qsort(word,coun,sizeof(word[0]),cmp);
    	for(int i=0;i<coun;i++)
    	printf("%s\n",word[i]);
    	char prefix[15];
    	while(scanf("%s",prefix)!=EOF)
    	printf("%d\n",search_w(prefix));
    	return 0;
    }

没办法，改思路。百度了一下，要用到字典树，用了后果断成功，至于字典树是什么，倒也很简单。不过不同人的代码实现，也不相同，各有优点吧。我的代码比较直观。

#include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    typedef struct Trie
    {
    	int v;
    	Trie *next[26];
    };
    Trie root;
    
    void createTrie(char *str)
    {
    	int len=strlen(str);
    	Trie *p=&root,*q;
    	for(int i=0;i<len;i++)
    	{
    		int id=str[i]-'a';
    		if(p->next[id]==NULL)
    		{
    	 		q=(Trie *)malloc(sizeof(root));//可以用q= new Trie代替
    	 		q->v=1;
    	 		for(int j=0;j<26;j++)
    	 		q->next[j]=NULL;
    	 		p->next[id]=q;
    	 		p=q;
    		}
    		else
    		{
    			p->next[id]->v++;//代表当前节点有几个词
    			p=p->next[id];
    		} 
    	}
    }
    int findTrie(char *str)
    {
    	int len=strlen(str);
    	Trie *p=&root;
    	for(int i=0;i<len;i++)
    	{
    		int id=str[i]-'a';
    		p=p->next[id];
    		if(p==NULL)
    	 	return 0;
    	}
    	return p->v;
    }  
    int main()
    {
    	char word[15];
    	for(int i=0;i<26;i++)
    	root.next[i]=NULL;
    	
    	while(gets(word)&&word[0]!='\0')
    	createTrie(word);
    	
     	memset(word, 0, sizeof(word));
    	  while(scanf("%s", word) != EOF)
        {
            int ans = findTrie(word);
            printf("%d\n", ans);
        }
    	return 0;
    }