Trie - Je3ter's Blog

int cnt,nxt[maxn][26];
bool exist[maxn];
void insert(string s,int l)
{
    int p=0;
    for(int i=0;i<l;i++)
    {
        int c=s[i]-'a';
        if(!nxt[p][c]) nxt[p][c]=++cnt;
        p=nxt[p][c];
    }
    exist[p]=1;
}
bool find(string s,int l)
{
    int p=0;
    for(int i=0;i<l;i++)
    {
        int c=s[i]-'a';
        if(!nxt[p][c]) return 0;
        p=nxt[p][c];
    }
    return exist[p];
}

P2580 于是他错误的点名开始了

题意

给出一些名字。每次询问一个名字，判断它是否在给出的名字之中以及是否是第一次出现。

题解

最直接的trie。将exist标记添加一种状态表示已访问过即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int cnt,nxt[maxn][26];
int exist[maxn];
void insert(string s,int l)
{
    int p=0;
    for(int i=0;i<l;i++)
    {
        int c=s[i]-'a';
        if(!nxt[p][c]) nxt[p][c]=++cnt;
        p=nxt[p][c];
    }
    exist[p]=1;
}
int find(string s,int l)
{
    int p=0;
    for(int i=0;i<l;i++)
    {
        int c=s[i]-'a';
        if(!nxt[p][c]) return 0;
        p=nxt[p][c];
    }
    if(exist[p]==1)
    {
        exist[p]=-1;
        return 1;
    }
    return exist[p];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        string s;cin>>s;
        int l=(int)s.size();
        insert(s,l);
    }
    int m;cin>>m;
    while(m--)
    {
        string s;cin>>s;
        int l=(int)s.size();
        int x=find(s,l);
        if(x==1) cout<<"OK"<<'\n';
        else if(x==0) cout<<"WRONG"<<'\n';
        else cout<<"REPEAT"<<'\n';
    }
    return 0;
}

P3879 [TJOI2010] 阅读理解

题意

给出 $n$ 个文本，每个文本包含一些文本串。给出 $m$ 个模式串。询问每个模式串在哪些文本中出现过。

题解

读错题了qwq。以为是每篇短文长度 $\leq 5\times 10^3$ 单词，算了一下对短文开trie的话空间会炸飞。所以我是以所有的询问建字典树，然后对短文中的每个单词进行匹配。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int id,cnt,nxt[maxn][26];
int exist[maxn];
void insert(string s,int l)
{
    int p=0;
    for(int i=0;i<l;i++)
    {
        int c=s[i]-'a';
        if(!nxt[p][c]) nxt[p][c]=++cnt;
        p=nxt[p][c];
    }
    exist[p]=++id;
}
int find(string s,int l)
{
    int p=0;
    for(int i=0;i<l;i++)
    {
        int c=s[i]-'a';
        if(!nxt[p][c]) return 0;
        p=nxt[p][c];
    }
    return exist[p];
}
string s0[10005];
vector<string> v[1005];
vector<int> a[10005],ans[10005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) 
    {
        int k;cin>>k;
        while(k--)
        {
            string s;cin>>s;
            v[i].push_back(s);
        }
    }
    int m;cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>s0[i];
        int l=(int)s0[i].size();
        insert(s0[i],l);
    }
    for(int i=1;i<=m;i++)
    {
        int l=(int)s0[i].size();
        a[find(s0[i],l)].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(auto j:v[i])
        {
            int l=(int)j.size();
            int x=find(j,l);
            for(auto k:a[x]) ans[k].push_back(i);
        }
    }
    for(int i=1;i<=m;i++)
    {
        int len=unique(ans[i].begin(),ans[i].end())-ans[i].begin();
        for(int j=0;j<len;j++) cout<<ans[i][j]<<' ';
        cout<<'\n';
    }
    return 0;
}

P2922 [USACO08DEC]Secret Message G

题意

给出一些文本串和一些模式串。对每个模式串，有多少文本串满足其前缀能与模式串匹配或其能与模式串前缀匹配。

题解

这题建trie时需要打两种不同的标记，分别代表前缀和完整的串。对每个串询问时，用其前缀与完整的串匹配，用完整的串与前缀匹配，然后去重一下就行了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int cnt,nxt[maxn][2];
int tot[maxn];
int exist[maxn];
void insert(string s,int l)
{
    int p=0;
    for(int i=0;i<l;i++)
    {
        int c=s[i]-'0';
        if(!nxt[p][c]) nxt[p][c]=++cnt;
        p=nxt[p][c];
        tot[p]++;
    }
    exist[p]++;
}
int find(string s,int l)
{
    int p=0,ans=0;
    for(int i=0;i<l;i++)
    {
        int c=s[i]-'0';
        if(!nxt[p][c]) return ans;
        p=nxt[p][c];
        ans+=exist[p];
    }
    return ans+tot[p]-exist[p];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m,n;cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        int k;cin>>k;
        string s;
        for(int j=1;j<=k;j++)
        {
            int x;cin>>x;
            s+=(char)('0'+x);
        }
        insert(s,k);
    }
    while(n--)
    {
        int k;cin>>k;
        string s;
        for(int j=1;j<=k;j++)
        {
            int x;cin>>x;
            s+=(char)('0'+x);
        }
        cout<<find(s,k)<<'\n';
    }
    return 0;
}

P3065 [USACO12DEC]First! G

题意

给出一些字符串。对每个字符串判断，是否能通过重排字母表顺序使其成为字典序最小的字符串。

题解

先将所有字符串插入trie，然后逐个检验。

其实就是修改一下find的过程。

若存在一个串为它的前缀，那么该串一定不能成为最小的字符串。
若相同层次上还有其它字符，那么该串的字符在新字典序下一定比它们小，分别连一条有向边。

最后在建出的图上跑一遍拓扑排序，看一下有没有环。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;
string s[30005];
int cnt,nxt[maxn][26];
bool exist[maxn];
bool ans[30005],g[26][26];
int in[26];
void insert(string s,int l)
{
    int p=0;
    for(int i=0;i<l;i++)
    {
        int c=s[i]-'a';
        if(!nxt[p][c]) nxt[p][c]=++cnt;
        p=nxt[p][c];
    }
    exist[p]=1;
}
bool find(string s,int l)
{
    int p=0;
    for(int i=0;i<l;i++)
    {
        if(exist[p]) return 0;
        int c=s[i]-'a';
        for(int j=0;j<26;j++)
            if(j!=c&&nxt[p][j]&&!g[c][j]) g[c][j]=1,in[j]++;
        p=nxt[p][c];
    }
    queue<int> q;
    for(int i=0;i<26;i++) 
        if(!in[i]) q.push(i);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v=0;v<26;v++)
            if(g[u][v]) 
            {
                in[v]--;
                if(!in[v]) q.push(v);
            }
    }
    for(int i=0;i<26;i++)
        if(in[i]) return 0;
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) 
    {
        cin>>s[i];
        int l=(int)s[i].size();
        insert(s[i],l);
    }
    for(int i=1;i<=n;i++)
    {
        memset(g,0,sizeof(g)),memset(in,0,sizeof(in));
        int l=(int)s[i].size();
        ans[i]=find(s[i],l);
    }
    int cnt=0;
    for(int i=1;i<=n;i++) 
        if(ans[i]) cnt++;
    cout<<cnt<<'\n';
    for(int i=1;i<=n;i++)
        if(ans[i]) cout<<s[i]<<'\n';
    return 0;
}

P3294 [SCOI2016]背单词

题意

给出 $n$ 个模式串。将模式串排序，每个模式串的权值被定义为：

若存在一个后缀排名比它大，权值为 $n\times n$ 。
若所有模式串都不是它的后缀，权值为它的排名。
若其所有后缀的排名都比它小，权值为它的排名与它后缀排名最大值的差。

题解

由上一题的启发，将输入的字符串翻转，就成了一个前缀的问题。我们用trie来处理字符串之间的前缀关系。具体地，我们将所有串插入trie。此时，trie上有字符串对应的点（即exist[i]非零），我们称为关键点。对于非关键点，我们利用并查集合并到它的关键点祖先上，对于关键点，我们由它的父亲向他连边。这样就可以将每个字符串与其前缀相连。

由此，我们得到了一棵树。按dfs序遍历这棵树，且优先遍历更小的子树就可以取得最优的结果了。

为什么按dfs序？可以这样理解：假定一棵子树还有结点 $u$ 未走，先走了另一棵子树的根结点 $v$ 。交换 $u,v$ ，它们自身的贡献没有变，但是 $v$ 子树中的点离 $v$ 更近了。
为什么按子树大小排序？每一棵子树都会对其余子树的根结点作出该子树大小的贡献。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=510005;
int id,cnt,nxt[maxn][26];
int exist[maxn];
int tot,f[maxn],siz[maxn],dfn[maxn];
ll ans;
vector<int> g[maxn];
int find(int x) {return f[x]==x?f[x]:f[x]=find(f[x]);}
void insert(string s,int l)
{
    int p=0;
    for(int i=0;i<l;i++)
    {
        int c=s[i]-'a';
        if(!nxt[p][c]) nxt[p][c]=++cnt;
        p=nxt[p][c];
    }
    exist[p]=id;
}
bool find(string s,int l)
{
    int p=0;
    for(int i=0;i<l;i++)
    {
        int c=s[i]-'a';
        if(!nxt[p][c]) return 0;
        p=nxt[p][c];
    }
    return exist[p];
}
void build(int x)
{
    for(int i=0;i<26;i++)
    {
        int c=nxt[x][i];
        if(c)
        {
            if(!exist[c]) f[c]=find(x);
            else g[exist[find(x)]].push_back(exist[c]);
            build(c);
        }
    }
}
bool cmp(int x,int y) {return siz[x]<siz[y];}
void dfs0(int u)
{
    siz[u]=1;
    for(auto v:g[u])
    {
        dfs0(v);
        siz[u]+=siz[v];
    }
    sort(g[u].begin(),g[u].end(),cmp);
}
void dfs(int u)
{
    dfn[u]=tot++;
    for(auto v:g[u])
    {
        ans+=tot-dfn[u];
        dfs(v);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        ++id;
        string s;cin>>s;
        reverse(s.begin(),s.end());
        int l=(int)s.size();
        insert(s,l);
    }
    for(int i=1;i<=cnt;i++) f[i]=i;
    build(0);
    dfs0(0);
    dfs(0);
    cout<<ans<<'\n';
    return 0;
}

P4407 [JSOI2009] 电子字典

题意

给出一些文本串，对每个模式串，判断是否存在文本串和它匹配或在它经过一次修改后能和它匹配的文本串的数量。修改操作定义为：

删除串中的某一个字母；
添加某一个字母；
替换某一个字母。

题解

考虑在查询的过程中引入这三种修改操作，实际上就是一个trie上dfs的过程。我们记录当前匹配的长度和是否进行过修改操作。

删除：留在该位置，当前匹配长度加一。
添加：枚举转移的后继结点，当前匹配长度不变。
修改：枚举转移的后继结点，当前匹配长度加一。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int cnt,nxt[maxn][26];
bool exist[maxn];
int l,tot,visx[10005];
bool vis[maxn];
string s;
void insert(int l)
{
    int p=0;
    for(int i=0;i<l;i++)
    {
        int c=s[i]-'a';
        if(!nxt[p][c]) nxt[p][c]=++cnt;
        p=nxt[p][c];
    }
    exist[p]=1;
}
bool find(int l)
{
    int p=0;
    for(int i=0;i<l;i++)
    {
        int c=s[i]-'a';
        if(!nxt[p][c]) return 0;
        p=nxt[p][c];
    }
    return exist[p];
}
void dfs(int x,int len,bool ok)
{
    if(len==l&&exist[x])
    {
        if(!vis[x]) vis[visx[++tot]=x]=1;
        return;
    }
    int c=s[len]-'a';
    if(!ok)
    {
        if(len<l) dfs(x,len+1,1);
        for(int i=0;i<26;i++)
            if(nxt[x][i]) 
            {
                dfs(nxt[x][i],len,1);
                dfs(nxt[x][i],len+1,1);
            }
    }
    if(len>=l) return;
    if(nxt[x][c]) dfs(nxt[x][c],len+1,ok);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        l=(int)s.size();
        insert(l);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>s;
        l=(int)s.size();
        if(find(l)) 
        {
            cout<<-1<<'\n';
            continue;
        }
        dfs(0,0,0);
        cout<<tot<<'\n';
        while(tot) vis[visx[tot--]]=0;
    }
    return 0;
}

P4551 最长异或路径

题意

给定一棵 $n$ 个点的带权树。寻找树中找两个结点，求最长的异或路径。

题解

记 $d(u,v)$ 表示 $u,v$ 路径边权异或和。一个重要的性质是 $d(u,v)=d(rt,u)\oplus d(rt,v)$ 。（ $rt$ 表示根结点）

那么对于每个 $d(rt,u)$ ，我们希望找到与它异或最大的 $d(rt,v)$ ，可以用trie来解决。具体地，我们将 $d(rt,u)$ 从高到低插入trie，每次查询时，我们尽可能走不同的后继结点，这样的结果一定是最优的。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int maxbit=31;
struct Edge {int to,next,w;} edges[maxn*2];
int cnt,head[maxn],a[maxn];
int nxt[31*maxn][2],num[31*maxn];
void insert(int x)
{
    int cur=1;
    for(int i=maxbit;i>=0;i--)
    {
        int bit=x>>i&1;
        if(!nxt[cur][bit]) nxt[cur][bit]=++cnt; 
        cur=nxt[cur][bit];
    }
    num[cur]=x;
}
int query(int x)
{
    int cur=1;
    for(int i=maxbit;i>=0;i--)
    {
        int bit=x>>i&1;
        if(nxt[cur][bit^1]) cur=nxt[cur][bit^1];
        else cur=nxt[cur][bit];
    }
    return x^num[cur];
}
void add(int u,int v,int w)
{
    edges[++cnt].w=w;
    edges[cnt].to=v;
    edges[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int fa)
{
    for(int e=head[u];e;e=edges[e].next)
    {
        int v=edges[e].to,w=edges[e].w;
        if(v==fa) continue;
        a[v]=a[u]^w;dfs(v,u);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v,w;cin>>u>>v>>w;
        add(u,v,w);add(v,u,w);
    }
    dfs(1,0);
    cnt=1;
    for(int i=1;i<=n;i++) insert(a[i]);
    int mx=0;
    for(int i=1;i<=n;i++) mx=max(mx,query(a[i]));
    cout<<mx<<'\n';
    return 0;
}

ACM

#Trie

Trie

https://je3ter.github.io/2023/06/22/ACM/Trie/

作者

Je3ter

发布于

2023年6月22日

许可协议

AtCoder Regular Contest 161 上一篇

Codeforces Round 881 (Div. 3) 下一篇