rt 100分:
#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int tr[N][28];
set<int> id[N];//有在这个位置结尾的单词的文章的编号
int n,m,tot;
char s[25];
inline void insert(int ID)
{
int p=0;
for(int i=1;s[i];i++)
{
int x=s[i]-'a';
if(!tr[p][x]) tr[p][x]=++tot;
p=tr[p][x];
}
id[p].insert(ID);
}
inline void Query()
{
int p=0;
for(int i=1;s[i];i++)
{
int x=s[i]-'a';
if(!tr[p][x]) return;
p=tr[p][x];
}
for(int a:id[p]) printf("%d ",a);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int l; scanf("%d",&l);
for(int j=1;j<=l;j++)
scanf("%s",s+1),insert(i);
}
scanf("%d",&m);
while(m--)
{
scanf("%s",s+1);
Query();
puts("");
}
return 0;
}
0分
/*
trie裸题
*/
#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int tr[N][28];
vector<int> id[N];//有在这个位置结尾的单词的文章的编号
int n,m,tot;
char s[25];
inline void insert(int ID)
{
int p=0;
for(int i=1;s[i];i++)
{
int x=s[i]-'a';
if(!tr[p][x]) tr[p][x]=++tot;
p=tr[p][x];
}
id[p].push_back(ID);
}
inline void Query()
{
int p=0;
for(int i=1;s[i];i++)
{
int x=s[i]-'a';
if(!tr[p][x]) return;
p=tr[p][x];
}
sort(id[p].begin(),id[p].end());
unique(id[p].begin(),id[p].end());
for(int a:id[p]) printf("%d ",a);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int l; scanf("%d",&l);
for(int j=1;j<=l;j++)
scanf("%s",s+1),insert(i);
}
scanf("%d",&m);
while(m--)
{
scanf("%s",s+1);
Query();
puts("");
}
return 0;
}
0分(2)
/*
trie裸题
*/
#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int tr[N][28];
vector<int> id[N];//有在这个位置结尾的单词的文章的编号
int n,m,tot;
char s[25];
inline void insert(int ID)
{
int p=0;
for(int i=1;s[i];i++)
{
int x=s[i]-'a';
if(!tr[p][x]) tr[p][x]=++tot;
p=tr[p][x];
}
id[p].push_back(ID);
}
inline void Query()
{
int p=0;
for(int i=1;s[i];i++)
{
int x=s[i]-'a';
if(!tr[p][x]) return;
p=tr[p][x];
}
sort(id[p].begin(),id[p].end());
unique(id[p].begin(),id[p].end());
for(int i=0;i<id[p].size();i++) printf("%d ",id[p][i]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int l; scanf("%d",&l);
for(int j=1;j<=l;j++)
scanf("%s",s+1),insert(i);
}
scanf("%d",&m);
while(m--)
{
scanf("%s",s+1);
Query();
puts("");
}
return 0;
}