题目链接
题目意思
统计以某个字符串为前缀的单词数
解题思路
最先看到这道题的时候想的就是字典树。但是这一次用字典树写一直内存超限。。。。 本来就特别讨厌字典树的题。唉。。。。烦死了。 不过后来发现用静态的数组就是过不了。后来发现有人写的博客用的是动态的，我就又改了改。 说起来也算有了解了一下动态的用法。 还有一个比较坑的就是这道题的输入。读到回车结束，换行再输入前缀。看到输入的时候又是一阵的头疼，不过也学到了另一种输入的方法吧！还算有收获。 话不多说了，我们下边就看看代码吧！
代码部分
#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;
}
