HDU1251 统计难题【字典树】

xiaoxiao2021-03-01  12

题目链接

题目意思

统计以某个字符串为前缀的单词数

解题思路

最先看到这道题的时候想的就是字典树。但是这一次用字典树写一直内存超限。。。。 本来就特别讨厌字典树的题。唉。。。。烦死了。 不过后来发现用静态的数组就是过不了。后来发现有人写的博客用的是动态的,我就又改了改。 说起来也算有了解了一下动态的用法。 还有一个比较坑的就是这道题的输入。读到回车结束,换行再输入前缀。看到输入的时候又是一阵的头疼,不过也学到了另一种输入的方法吧!还算有收获。 话不多说了,我们下边就看看代码吧!

代码部分

#include <iostream> #include <sstream> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <cstring> #include <map> #include <algorithm> using namespace std; const int maxn=15; const int son=26; struct Trie { int cnt; Trie *nex[son]; }; int top; int idx(char c) { return c-'a'; } Trie *CreatTrie() { Trie *p=(Trie *)(malloc)(sizeof(Trie)); p->cnt=0; for(int i=0; i<son; i++) p->nex[i]=NULL; return p; } Trie *Init() { top=0; return CreatTrie(); } void Insert(Trie *root,string s) { Trie *p=root; for(int i=0; i<s.size(); i++) { int temp=idx(s[i]); if(p->nex[temp]==NULL) { p->nex[temp]=CreatTrie(); } p=p->nex[temp]; p->cnt++; } } int Search(Trie *root,string s) { Trie *p=root; for(int i=0; i<s.size(); i++) { int temp=idx(s[i]); if(p->nex[temp]==NULL) return 0; p=p->nex[temp]; } return p->cnt; } int main() { ios::sync_with_stdio(false); string s; Trie *root=Init(); while(getline(cin,s,'\n')&&s.size()!=0) Insert(root,s); while(cin>>s) cout<<Search(root,s)<<endl; return 0; }
转载请注明原文地址: https://www.6miu.com/read-4200183.html

最新回复(0)