Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 字典树一直TLE，求教

Posted by Mangata at 2020-06-24 13:13:42 on Problem 2503
```#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=200010;
int tree[maxn][30]={0},flag[maxn]={0};
int cnt=0;
string ch[maxn];
char str[100],ch1[100];
int insert(int l,int r)
{
int root=0;
for(int i=l;i<r;++i)
{
int id=str[i]-'a';
if(!tree[root][id]) tree[root][id]=++cnt;
root=tree[root][id];
}
flag[root]=1;
return root;
}
void find(int l,int r)
{
int root=0;
for(int i=l;i<=r;++i)
{
int id=ch1[i]-'a';
if(!tree[root][id])
{
puts("eh");
return;
}
root=tree[root][id];
}
if(flag[root])
cout<<ch[root],putchar('\n');
else
puts("eh");
}
int main(void)
{

while(gets(str)!=NULL&&str[0])
{
memset(ch1,0,sizeof(ch1));
int len=strlen(str);
for(int i=0;i<len;++i)
{
if(str[i]==' ')
{
ch[insert(i+1,len)]=ch1;
break;
}
else
ch1[i]=str[i];
}
}
while(~scanf("%s",ch1))
{
int len2=strlen(ch1)-1;
find(0,len2);
}
return 0;
}```

Followed by:

User ID:
Title:

Content: