Tag-Trie

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2020-09-14 20:27:32 |  0 Comments  |  字符串 Trie 后缀自动机

Nowcoder Mutischool-training 4 C Counting New String 广义后缀自动机

题目大意

对S串做两次f变换,得到一个字符串集A,求A中本质不同的字符串数量。

题解

其实不管是观察,还是拿样例手算,最后一定能得出一个结论:

其实两次f变换和一次f变换的作用是一样的。

所以只需要看一下一次f变换就行了。

f其实是对子串的变换,后面被变换的字符只跟其前面的字典序比他大的字符有关。

先看题目要求,求A中本质不同的字符串数量。

前面说了A实际上是S的所有子串做了变换而已。所以也就是本质不同的类子串数量(这个说法大概可以吧)。所以很自然想到这是一个后缀自动机。

但是这里的要求的并不是简单的子串,需要做变化。

前面说了,被变换的字符只跟其前面的字典序比他大的字典序最大的字符有关,只要出现一个比他大的字符就要重新更新字符串。

于是我们可以这样搞:

我们考虑将原串倒过来,然后按照题目的要求去建一个Trie,具体建法比较麻烦,如果当前字符的上一个比他大的字符没有出现,则需要从根开始往下重新建一条链,否则就继续往下建,复杂度最大为O(10n),但实际上肯定到不了。

然后对Trie静态建广义后缀自动机,直接跑本质不同子串数量即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e6+5;
string s;
char ss[maxn];
int len;
int son[maxn][10],fa[maxn],cl[maxn];
int now = 1;
int root = 1;
struct SAM{
    int tot;
    int pos[maxn],link[maxn],maxlen[maxn],trans[maxn][10];
    queue<int>q;
    ll ans;
    void init(){
        tot = 1;
        return;
    }
    int extend(int ch,int last){
        int x,y,z = ++tot;
        int p = last;
        maxlen[z] = maxlen[last]+1;
        while(p && !trans[p][ch])
            trans[p][ch] = z
 2020-02-19 22:10:38 |  0 Comments  |  字符串 可持久化线段树 可持久化数据结构 Trie

Codeforces 547E Mike and Friends AC自动机Fail树上DFS序建可持久化线段树

Input

5 5
a
ab
abab
ababab
b
1 5 1
3 5 1
1 5 2
1 5 3
1 4 5

Output

7
5
6
3
6

题目大意

给出n个字符串,q次询问,每次询问l,r,k,求问

字符串l——r中,包含字符串k(字符串k作为子串)的字符串个数是多少。

题解

多模式串匹配肯定是AC自动机

但是这个问题是多个串中有多少能匹配到当前询问的这一个字串的问题,而不是经典的某个串能匹配多少个已经给出的串的问题。

AC自动机的Trie树中,某个节点的所有祖先节点表示一个或几个字符串在当前这个位置之前的字符串前缀。所以对于某个结束节点来说,他的所有祖先节点加上他本身构成了一个字符串。

而对于AC自动机建立的fail树来说,一个节点的fail指针指向的节点以及其trie树上的祖先一定构成了当前节点到trie树的根节点所表示的字符串的一个后缀。如果其fail指针指向的是一个结束节点,那么这个串就一定能匹配它的fail指针指向节点在trie树所代表的一个字符串,也就是完成了一个子串匹配。

于是我们可以借助这一点性质,来求解能匹配ac自动机中第k个字符串的字符串个数,方法是:

沿着当指向当前节点的fail路径的反方向走,每走到一个节点ans+1,最终无路可走时,得到的就是答案。(包括这个字符串本身)。、

但是这个题还有在区间[l,r]的字符串的限制。

考虑到普通的线段树没法做到这种询问,所以我们应该想到这个题可以用可持久化线段树来做。

可持久化线段树最大的特点就是每棵线段树的根节点都代表着一次更新的时间戳,我们可以利用这个时间戳去求区间的一个值。

但是这是一个AC自动机上的问题,准确的来说是fail树上的问题,如何建线段树?

对于树上问题,可以先想树链剖分,其本质就是求DFS序,所以我们也可以对fail树构建DFS序,然后在此基础依次添加每个串,构建可持久化线段树。

根据上面的fail树上的性质来说,通过fail路径的反方向路径构成的fail树,某个节点的子节点都是原先的fail指针指向当前节点的节点,也是我们要统计路径时走向的节点。

某个节点的子树,代表了能匹配到以此节点到trie树根节点构成的字符串的后缀的所有字符串所在的fail树的位置。

我们根据fail路径来构建DFS序,在此基础上建立可持久化线段树。在建立可持久化线段树的过程中,每添加一个字符串,都要对这个字符串在AC自动机Trie树上

 2020-02-11 17:05:57 |  0 Comments  |  Trie

CodeForces - 1055F Tree and XOR 01-Trie

题目大意

有n个节点的有根树,根为1,每条边有权值,点对(u,v)的路径长度为从u到v路径上所有权值的异或值,认为点对(u,v)与(v,u)表示两个路径,总共有n2个点对路径(自己到自己也算一个),求问其中路径长度第k小的路径长为多少。

题解

n的范围是很大的,不可能通过枚举计算。

两点(u,v)之间的路径长度,可以通过lca转化为:

(u,lca) xor (v,lca) = (u,lca) xor (lca,root) xor(lca,root) xor (v,lca) = (u,root) xor (v,root);

所以可以将每个点到根节点的路径异或长度预处理出来,之后再进行下面的操作。

建立一个01Trie,我们可以有办法求得路径异或长度不超过某个值val的路径数目。

对于当前位bit,我们去检查小于之前已经决定的答案ans加1<<bit的值的个数。也即当前的二进制位上的数为0的个数。

如果这个个数size小于k,说明答案应该是大于等于ans + (1<<bit)的,于是就决定当前的二进制位为1,k -= size,进入当前层表示为1的子树内再向下搜寻。

否则就直接进入当前层表示为0的子树内再向下搜寻。

整个搜寻答案的过程是O(62·n)的。加二分实际上是没意义的。

最后的一个问题就是,空间明显不允许我们开这样一个完整的Trie,所以需要动态建立每一层的Trie节点,用到什么建什么,不用的不管,搜寻下一层的时候要将上一层的节点表示清空。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll k;
int id;
const int maxn = 1e6+5;
ll v[maxn];
int pre[maxn];
int tot = 0;
ll siz[maxn];
int son[maxn][2];
int a[maxn],b[maxn];
void init(){
    for(int i = 1;i <= n;++i)
        son[i][0] = son[i][1] = 0,siz[i] = 0;
    tot = 0;
}
int new_tag(int now,int ch){
    if(!son[now][ch])
        son[now]
 2020-02-06 20:52:24 |  0 Comments  |  最小生成树 Trie

51Nod 1601 完全图的最小生成树计数 kruskal + trie异或运算贪心

题解

每条边的权值都是根据每个点的定值通过二进制异或得出的。

如果有两个点的数二进制高k位相等,那么我们如果要想要把这两个点的边加入最小生成树,那么花费的代价是与高k位无关的。

假设在第k+1位发生分歧,则这条边的最小权值即为这一位对应的二进制值。然后要做的就是继续向更低位检查。

这明显是个递归过程,而且很容易能想到这个过程是与01Trie的节点访问实际上是一样的。

于是所有的答案统计全部都在01trie上。

接下来看kruskal算法的核心:每一次将最小边权的边试图加入最小生成森林。

所以我们必然优先去找01Trie中同一个叶子节点上的点对的边。

假如一个叶节点上有k个点(k > 2),那么对应的建边方案就是kk-2种。

当从叶节点向上走的时候,假设某节点的父亲节点的两个子树上都有点存在(即两个子树都非空),那么我们肯定要用边把这两个子树连起来,连起来的时候就需要顺着trie往下找异或值最小的边的权值是多少。

细节不是很好解释,不过这种思路是二进制异或时一种常见的贪心思路,可以看代码理解一下。

这个题不需要并查集,因为当刚向上走到某个点时,如果其两个子树都非空,那么这两个子树代表的两个已经构建好的生成树必然属于两个不同的连通块。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PI;
const int maxn = 1e5+5;
const int INF = 2e9;
const ll MOD = 1e9+7;
int n, sz, fac[35], rt;
ll ans,sum;
struct tree{
    int l, r, cnt;
} tr[maxn*30];
ll quick_pow(ll x, ll y){
    ll ans = 1;
    while (y){
        if (y & 1)
            ans = ans * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return ans;
}
void insert(int &d, int dep, int v){
    if (!d)
        d = ++sz;
 2019-09-06 22:19:42 |  0 Comments  |  Trie 思维题 hash

2018 ACM/ICPC Asia Jiaozuo Regional K.Counting Failures on a Trie Trie 思维题 倍增 Hash

题目大意

给出一棵trie树和一个字符串,然后对于每一次询问l,r,在Trie树上对子串[l,r]进行匹配。如果在某个字符处失配,则重新跳回Trie树根节点并忽略这个字符继续匹配。

求问对于每一个询问,在匹配过程中会失配几次,且最终会到达哪个节点。

题解

暴力搜索必然是n^2的,对于此题1e5还有多组数据的情况想都不要想。

而每一次失配我们都会重新回到起点。

于是我们可以用预处理从每个位置的下一个位置开始的子串第一次的失配位置是在原字符串中的哪个位置。由于在这个位置我们会失配回到起点然后再次从这个位置的下一个位置开始,所以应该可以想到这个失配过程是完全可以去倍增的!。我们可以用倍增来处理失配次数,然后最终位置可以直接通过一个map存储hash值对应的trie树位置进行查询。

然后考虑如何预处理。

首先我们应该能够想到,如果一个子串能够在trie树中成功匹配,那么它的前缀串也一定能够在trie树中成功匹配。

于是这个性质导致我们可以二分失配的长度,然后我们只需要查询当前二分产生的子串是否能在trie树中进行匹配就可以了。

hash想不被卡的话,感觉就是选一个奇怪点的质数作为base。取模倒是不至于,直接unsigned long long自然溢出就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef unsigned long long ll;
const ll base = 983;
ll h[maxn],bs[maxn];
struct trie{
    int id;
    int ch[26];
}tr[maxn];
int f[maxn][26];
string s;
int x;char c;
int len;
map<ll,int>mp;
int n,m,q,t;
int ql,qr;
void init(){
    bs[0] = 1;
    for(int i = 1;i < maxn;++i){
        bs[i] = bs[i-1] * base;
    }
    return;
}
ll get_hash(int l,int r){
    return h[r] - h[l] * bs[r - l];
}
void dfs(int
 2019-08-06 21:47:45 |  0 Comments  |  Trie

2019 Multi-University Training Contest 5 1002 three arrays Trie树+思维题

题目大意

给出两个长度为n的序列a,b,重新排列a、b使得两个序列各个位置上的数异或起来得到的序列C字典序最小,并输出最小字典序的c

题解

这题思路甚为巧妙。

关于异或的题目,我们总是分为各个二进制位置上的0/1来看,例如线性基、0/1Trie。此题就是通过0/1Trie来实现的。

首先我们对于两个序列,建立两个0/1Trie。

然后我们首先从第一个Trie中找出一个数,放入当前的候选答案的栈内,之后去另外一棵Trie中找与之异或值最小的数,再放入栈中,再去当前找到的值所在Trie的另一棵Trie中找与之异或值最小的数放入栈中,如此往复。

直到我们找到一个长度为2的环,此时这个长度为2的环中的两个数就是c中的一组答案了。因为他们两个相互为异或的最小值。就把他们存入c,并且从栈中pop掉,并将这两个数在自己的Trie树中删除,继续循环上面的步骤。

按照这种方法,直到我们把所有n个异或值都找出来,后面只需要排一遍序就是我们需要的最终答案了。

至于为什么环的长度一定为2而不可能为更多,这个东西是有证明的,不过暂时还没理解,暂时不写了。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+10;
int ch[maxn*32][2],cnt[maxn*32][2];
int n,T;
int v,c[maxn];
int tot = 0
 2019-08-03 20:32:45 |  0 Comments  |  Trie 贪心 启发式合并

Codeforces 965E Short Code Trie树+贪心(启发式合并)

题目大意

给你n个串,让你用每个串的某个前缀串重命名这个串并保证重命名后不会有重复的字符串。

题解

题目很显然需要我们处理n个串的前缀,所以很自然的想到用Trie树(字典树)来降低时间复杂度和空间复杂度。

所以我们先对n个串建立一棵Trie树,然后在这个Trie树上进行操作。

很多人都说后面是启发式合并,我也不是很清楚下面的思路算不算是启发式合并。

后面我们直接dfs整棵Trie树,并自叶节点向上维护信息。

对于每一个节点,维护一个大根堆(用优先队列实现即可),记录其与其子树上的所有的字符串的长度,若我们没有把某个字符串缩到当前节点,那么我们就将子树中深度最深节点所表示的字符串重命名为当前节点所表示的字符串,并回溯更新父节点的信息。

最终回溯到根后,直接将根所有的大根堆内维护的所有的字符串的深度(也就是最终长度)加入答案,最终输出就可以了。

最终的时间复杂度大概是O(nlogn)

代码

#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn = 1e5+5;
string s[maxn];
int cnt = 0;
struct tree_node{
    int ch[26];
    int dep;
    int en;
}tr[maxn<<4];
int dep[maxn];
typedef pair<int,int>PI;
priority_queue<PI>q[maxn];
int ans = 0;
void build(int x,int now,int depth){
    int len = s[x].size();
    for(int i = 0;i < len;++i){
        char t = s[x][i];
        if(tr[now].ch[t - 'a'] == -1){
            tr[now].ch[t-'a'] = ++cnt;
            tr[cnt].dep = tr[now].dep + 1;
            for(int i = 0;i < 26;++i)
                tr[cnt].ch[i] = -1;
            tr[cnt].en = 0;
        
 2019-04-06 15:14:55 |  0 Comments  |  字符串 Trie

poj - IMMEDIATE DECODABILITY Trie树模板

 题解

本题为Trie(字典树)的模板题。

我们先来说一下Trie的基本构造:

Trie树,又名字典树,故名思义,将字符串各个字符以类似字典的方式构造成一棵树,以便检索。

Trie树的每一个节点的深度代表着当前检索到的字符串的长度。而Trie树的每两个节点之间的边可以认为是代表着字典中的一个字符。

字典树的根节点是我们检索字符串的起始,我们每次检索字符串都是由这个根节点开始的。我们每检索一个字符,就顺延着当前这个字符所代表的边走向下一个节点。

有些节点会打一个flag标记,这代表着Trie树中一个单词的结束。

以上是Trie树的基本构造。

对于这个题目,它的要求是判断任意一个字符串不能是另外任意一个字符串的前缀。

所以我们对每个节点加一个cnt标记统计在建立Trie树过程中当前节点的访问次数。

所以题意在我们的思路中,就变为了:

在建Trie树的过程中,如果当前访问的节点打上了flag标记(一个单词的结尾)并且访问次数大于了1,则说明出现一个单词为其它单词的前缀。就输出not immediately decodable,如果建完Trie都不存在这样的单词,就输出immediately decodable。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
string s;
int num = 0;
const int maxn = 10005;
struct trie{
    int cnt;
    bool flag;
    int child[2];
}pool[maxn],root;
bool pp = false;
void init(){
    memset(pool,0,sizeof(pool));
    num = 0;
    root = pool[0];
    pp = false;
    return;
}
int sum = 0;
int main(){
    init();
    while(cin >> s){
        int len = s.size();
        if
Title - Artist
0:00