警钟trie烂
查看原帖
警钟trie烂
749630
wxzzzz楼主2023/7/31 22:28

如果你写的 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;
}
2023/7/31 22:28
加载中...