社区讨论
Trie全RE求助
P3879[TJOI2010] 阅读理解参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lprpbzyu
- 此快照首次捕获于
- 2023/12/05 10:09 2 年前
- 此快照最后确认于
- 2023/12/05 16:04 2 年前
玄关
CPP#include<bits/stdc++.h>
//#define int __int128
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),
ch=getchar();
return x*f;
}
inline void write(int n)
{
if(n<0)
n=-n,
putchar('-');
if(n>=10)
write(n/10);
putchar(n%10+'0');
return ;
}
const int N=10010;
struct node
{
int child[30];
bool cnt[1010];
}Trie[N];
int n,m;
int tot=1;
int st[N],top=0;
void insert(string s,int art)
{
int cur=0;
for(int i=0;s[i];i++)
{
if(Trie[cur].child[s[i]-'a']==0)
Trie[cur].child[s[i]-'a']=tot++;
cur=Trie[cur].child[s[i]-'a'];
}
Trie[cur].cnt[art]=1;
return ;
}
void query(string s)
{
int cur=0,flag=0;
for(int i=0;s[i];i++)
{
if(Trie[cur].child[s[i]-'a']==0)
{
flag=1;
break;
}
cur=Trie[cur].child[s[i]-'a'];
}
if(flag)
{
putchar('\n');
return ;
}
top=0;
bool f=0;
for(int i=1;i<=n;i++)
if(Trie[cur].cnt[i])
{
if(f) putchar(' ');
else f=1;
write(i);
}
if(top)
write(st[0]);
for(int i=1;i<top;i++)
putchar(' '),
write(st[i]);
putchar('\n');
return ;
}
signed main()
{
n=read();
for(int i=1;i<=n;i++)
{
int L=read();
while(L--)
{
string s;
cin>>s;
insert(s,i);
}
}
m=read();
map<string,bool> dic;
while(m--)
{
string s;
cin>>s;
if(dic[s])
continue;
dic[s]=1;
query(s);
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...