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

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

题目大意

给定一棵树,每个节点上有一个大写字母,共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] = s[x];
				s[y].len = s[p].len + 1;
				s[y].endpos = 0;
				s[z].link = s[x].link = y;
				while(p && s[p].trans[c] == x){
					s[p].trans[c] = y;
					p = s[p].link;
				}
			}
		}
		return z;
	}
	void dfs(int now,int fa){
		f[now][0] = fa;
		for(int i = h[now];i != -1;i = next[i]){
			dfs(to[i],now);
			s[now].endpos += s[to[i]].endpos;
		}
	}
	void build(){
		for(int i = 2;i <= siz;++i){
			if(s[i].link)
				add(s[i].link,i);
		}
		dfs(1,0);
		for(int j = 1;j <= 20;++j){
			for(int i = 1;i <= siz;++i)
				f[i][j] = f[f[i][j-1]][j-1];
		}
	}
	int query(int u,int len){
		for(int i = 20;i >= 0;--i)if(s[f[u][i]].len >= len)u = f[u][i];
		return s[u].endpos;
	}
}sam;
int insert_trie(int u,char ch){
	int c = ch - 'A';
	if(!tr[u][c])tr[u][c] = ++tot;
	u = tr[u][c];
	cnt[u]++;
	return u;
}
queue<int>qe;
void bfs(){
	qe.push(root);
	sam_pos[root] = 1;
	while(!qe.empty()){
		int now = qe.front();
		qe.pop();
		for(int i = 0;i < 26;++i){
			int ch = tr[now][i];
			if(!ch)continue;
			qe.push(ch);
			sam_pos[ch] = sam.extend(sam_pos[now],i,cnt[ch]);
		}
	}
	return;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	cin >> s;
	root = tot = 1;
	sam.init();
	trie_id[1] = insert_trie(root,s[0]);
	for(int i = 2;i <= n;++i){
		cin >> l;
		trie_id[i] = insert_trie(trie_id[l],s[i-1]);
	}
	bfs();
	sam.build();
	while(q--){
		cin >> x >> l;
		cout << sam.query(sam_pos[trie_id[x]],l) << "\n";
	}
	return 0;
}


Pre: No Post
Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00