如果你写的 trie,并且直接记录每个单词所在的每个文章,一定要判重,一个单词可能会在一篇文章内出现多次。
WA:
#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 1000005
using namespace std;
inline ll read()
{
rll x=0;bool f=1;register char c=getchar();
while(c<48||c>57){if(c=='-') f=0;c=getchar();}
while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
return f?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
ll n=read(),m,idx,trie[N][30];
vector<ll> pos[N];
char s[N];
inline void insert(char ch[N],ll id)
{
rll p=0;
for(rll i=0;ch[i];i++)
{
rll c=ch[i]-97;
if(!trie[p][c]) trie[p][c]=++idx;
p=trie[p][c];
}
pos[p].push_back(id);
}
inline ll query(char ch[N])
{
rll p=0;
for(rll i=0;ch[i];i++)
{
rll c=ch[i]-97;
if(!trie[p][c]) return 0;
p=trie[p][c];
}
return p;
}
int main()
{
for(rll i=1;i<=n;i++)
{
m=read();
while(m--)
{
scanf("%s",s);
insert(s,i);
}
}
m=read();
while(m--)
{
scanf("%s",s);
cll id=query(s);
if(id)
{
for(rll i=0;i<pos[id].size();i++)
write(pos[id][i]),putchar(' ');
}
putchar('\n');
}
return 0;
}
AC:
#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 1000005
using namespace std;
inline ll read()
{
rll x=0;bool f=1;register char c=getchar();
while(c<48||c>57){if(c=='-') f=0;c=getchar();}
while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
return f?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
ll n=read(),m,idx,trie[N][30];
vector<ll> pos[N];
map<pair<ll,ll>,bool> flag;
char s[N];
inline void insert(char ch[N],ll id)
{
rll p=0;
for(rll i=0;ch[i];i++)
{
rll c=ch[i]-97;
if(!trie[p][c]) trie[p][c]=++idx;
p=trie[p][c];
}
if(!flag[{p,id}]) //判重
pos[p].push_back(id),flag[{p,id}]=1;
}
inline ll query(char ch[N])
{
rll p=0;
for(rll i=0;ch[i];i++)
{
rll c=ch[i]-97;
if(!trie[p][c]) return 0;
p=trie[p][c];
}
return p;
}
int main()
{
for(rll i=1;i<=n;i++)
{
m=read();
while(m--)
{
scanf("%s",s);
insert(s,i);
}
}
m=read();
while(m--)
{
scanf("%s",s);
cll id=query(s);
if(id)
{
for(rll i=0;i<pos[id].size();i++)
write(pos[id][i]),putchar(' ');
}
putchar('\n');
}
return 0;
}