Tag-后缀自动机

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

 2021-01-16 21:50:05 |  0 Comments  |  后缀自动机

ICPC2019 Xuzhou L.Loli, Yen-Jen, and a cool problem

题目大意

给定一棵树,每个节点上有一个大写字母,共q次询问,每次询问包含两个参数X,L,表示求这个树中(由底向上)的字符串有多少和从X向上L的字母拼接成的字符串相同。

题解

广义后缀自动机模板题。

实际上就是求一个子串在所有的字符串中出现的次数,也就是endpos集大小。

注意在找这个具体的字符串对应的状态节点时,要倍增的在后缀树中往上跳。

剩下的就真的只是模板。

代码

#include <bits/stdc++.h>
using namespace std;
struct SAM_node{
	int len,endpos,trans[26],link;
};
const int maxn = 3e5+5;
int tr[maxn][26],tot = 0,trie_id[maxn],sam_pos[maxn],cnt[maxn],root;
string s;
int n,q;
int x,l;
struct SAM{
	SAM_node s[maxn<<1];
	int h[maxn<<1],next[maxn<<1],to[maxn<<1];
	int siz,sum,f[maxn<<1][21];
	void add(int u,int v){
		to[sum] = v;next[sum] = h[u];h[u] = sum++;
		return;
	}
	void init(){
		siz = 1;
		sum = 0;
		memset(h,-1,sizeof(h));
		return;
	}
	int extend(int last,int c,int num){
		int z = ++siz;
		int p = last;
		s[z].len = s[p].len + 1;
		s[z].endpos = num;
		while(p && !s[p].trans[c]){
			s[p].trans[c] = z,p = s[p].link;
		}
		if(!p)
			s[z].link = 1;
		else{
			int x = s[p].trans[c];
			if(s[x].len == s[p].len + 1)
				s[z].link = x;
			else{
				int y = ++siz;
				s[y] = 
 2020-10-04 22:00:01 |  0 Comments  |  后缀自动机

后缀自动机模板2 统计某一子串出现次数

题解

其实就是每个字符串的endpos集的大小,无非就是同长度取max而已

我们注意到,如果一个字符串在st状态中出现,其必在trans决定的后续状态中继续出现。且每次在st状态中新出现的字符串,一定是以转移过来的节点的字符串做前缀的。

所以我们把每个非clone节点的位置的值设为1,clone节点的位置的值设为0,直接用后缀链link构成的DAG上跑拓扑DP就可以了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;
char ss[maxn];
typedef long long ll;
int len;
struct SAM{
    int tot;
    int pos[maxn],link[maxn],trans[maxn][26],maxlen[maxn];
    queue<int>q;
    vector<int>g[maxn];
    int indeg[maxn];
    ll ans1;
    ll ans[maxn],endpos[maxn];
    int last;
    void init(){
        last = tot = 1;
        return;
    }
    int extend(int ch){
        int x,y,z = ++tot;
        int p = last;
        endpos[z] = 1;
        maxlen[z] = maxlen[last] + 1;
        while(p && !trans[p][ch])
            trans[p][ch] = z,p = link[p];
        if(!p){
            link[z] = 1;
        }
        else{
            x = trans[p][ch];
            if(maxlen[p] + 1 == maxlen[x])
                link[z] = x;
            else{
                y = ++tot;
            
 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
Title - Artist
0:00