593
HDU 1251
//这题不仅仅只是字符串处理一下那么简单，字典树。。。不然狂超时。。。。。。。。。。。
//字典树的代码,基础字典树
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
struct dictree
{
struct dictree *child[26];
int n;
};
struct dictree *root;
void insert (char *source)
{
int len,i,j;
struct dictree *current,*newnode;
len=strlen(source);
if(len==0) return;
current=root;
for(i=0;i<len;i++)
{
if(current->child[source[i]-'a']!=0)
{
current=current->child[source[i]-'a'];
current->n=current->n+1;
}
else
{
newnode=(struct dictree *)malloc(sizeof(struct dictree));
for(j=0;j<26;j++)
newnode->child[j]=0;
current->child[source[i]-'a']=newnode;
current=newnode;
current->n=1;
}
}
}
int find(char *source)
{
int i,len;
struct dictree *current;
len=strlen(source);
if(len==0) return 0;
current=root;
for(i=0;i<len;i++)
{
if(current->child[source[i]-'a']!=0)
current=current->child[source[i]-'a'];
else return 0;
}
return current->n;
}
int main()
{
char temp[11];
int i,j;
root=(struct dictree *)malloc(sizeof(struct dictree));
for(i=0;i<26;i++)
root->child[i]=0;
root->n=2;
while(gets(temp),strcmp(temp,"")!=0)
insert(temp);
while(scanf("%s",temp)!=EOF)
{
i=find(temp);
printf("%d\n",i);
}
}
//超时的。。。。。
#include "stdio.h"
const int MAX=9999999;
char words[MAX][12]; //全局变量已初始化
char prefix[12];
int main()
{
char ch,temp='\0';
int count=0; //count代表单词数
int i=0,j; //i---字母指针
while(scanf("%c",&ch)!=EOF)
{
if(ch=='\n' && temp=='\n')
break;
else if(ch=='\n' && temp!='\n')
{
count++;
i=0;
}
else
words[count][i++]=ch;
temp=ch;
}
//testprint
//for(i=0;i<count;i++)
//printf("%s\n",words[i]);
int sum;
while(scanf("%s",prefix)!=EOF)
{
sum=0;
for(i=0;i<count;i++)
{
for(j=0;prefix[j]!='\0';j++)
if(words[i][j]!=prefix[j])
break;
if(prefix[j]=='\0')
sum++;
}
printf("%d\n",sum);
}
return 0;
}
最后更新：2017-04-02 15:15:09