统计难题
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others)
Total Submission(s): 24521 Accepted Submission(s): 10133Problem DescriptionIgnatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).Input输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.注意:本题只有一组测试数据,处理到文件结束.
Output对于每个提问,给出以该字符串为前缀的单词的数量.Sample InputbananabandbeeabsoluteacmbabbandabcSample Output231AuthorIgnatius.L
坑坑：用G++在杭电oj上提交会一直内存超限～
#include<iostream>
#include<vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <math.h>
#include<algorithm>
#define ll long long
#define eps 1e-8
using namespace std; struct nodes
{
int cnt;
struct nodes *next[];
nodes()
{
int i;
cnt = ;
for(i = ; i < ; i++)
next[i] = NULL;
}
} root,*temp; void inserts(char *word)
{
nodes *cur = &root;
while(*word )
{
int t = *word - 'a';
if(cur->next[t] == NULL)
{
temp = (nodes *)malloc(sizeof(nodes));
temp->cnt = ;
for(int i = ; i < ; i++)
temp->next[i] = NULL;
cur->next[t] = temp;
}
cur = cur->next[t];
cur->cnt++;
word++;
}
} void searchs(char *word)
{
nodes *cur = &root;
int ans = ;
while(*word && cur)
{
cur = cur->next[*word - 'a'];
if(cur)
ans = cur->cnt;
else
{
ans = ;
break;
}
word++;
}
printf("%d\n",ans);
} int main(void)
{
char bank[];
char ss[]; while(gets(bank) && bank[] )
{
inserts(bank);
}
while(scanf("%s",ss) != -)
{
searchs(ss);
}
return ;
}
新增省内存方法，STL中的map:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#define N 500015
#define INF 1000000
#define ll long long
using namespace std; int main(void)
{
map<string,int>Q;
char temp[];
int l;
while(gets(temp) && temp[])
{
l = (int)strlen(temp);
for(int i = l; i > ; i--)
{
temp[i] = '\0';
Q[temp]++;
}
}
while(scanf("%s",temp) != -)
{
printf("%d\n",Q[temp]);
}
return ;
}