从BZOJ3881谈fail树的应用

tonyfang posted @ 2016年12月18日 20:43 in 随笔 with tags C++ OI , 1706 阅读

前一篇文章已经比较详细地说过fail树的应用了。

这里从一道题目(BZOJ 3881)来更深地谈fail树的应用。

首先看题目:

Alice和Bob在玩游戏,Alice有一个字符串集合S包含n个字符串,Bob往它的集合里添加字符串,并间歇询问:当前S集合的第i个字符串被T中的几个串包含?

$n, q \leq 10^5, all~in~S \leq 10^6, all~in~T \leq 10^6$

第一遍看题,需要注意的是,本题与BZOJ2434阿狸的打字机不同,是统计匹配的个数,而不是匹配的次数

如果是匹配次数的话,我们处理出来每条链到哪里,然后加起来就行了。

但是统计个数呢?考虑同样处理出每条链到哪里,然后呢?

求树链的并!

那怎么办呢?树链剖分?No!DFS序!

上篇文章说过,DFS序+fail树是常见的方法。那么本题考虑采用DFS序,然后呢?

我们把每个点找出来,然后单点加即可。

那么重复的呢?按照DFS序的进入顺序排个序,然后呢?每两个找LCA,LCA处-1即可。

这里找LCA要用RMQ方法(zkw线段树),其他会TLE。

(P.S. 这里的zkw线段树是从wyfcyx那里copy的,有空学学)

就是用一种类似于虚树的方法来解决问题。

如果是求答案,只要输出[in[x],out[x]]内的和即可。

代码很长……用namespace来结构化。

 

# include <queue>
# include <stdio.h>
# include <string.h>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 2000010;
const int N = 27;

// ==== Graph ==== //
# define next NEXT
int head[M<<1], next[M<<2], to[M<<2];
int in[M], out[M], dep[M], tDFN=0, tot=0;
inline void add(int u, int v) {
	++tot;
	next[tot] = head[u];
	head[u] = tot;
	to[tot] = v;
}
inline void adde(int u, int v) {
//	printf("add edge: u, v %d %d\n", u, v);
	add(u, v); add(v, u);
}
inline void dfs(int x, int fa) {
	in[x] = ++tDFN;
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa) continue;
		dep[to[i]] = dep[x]+1;
		dfs(to[i], x);
	}
	out[x] = tDFN;
}
// ==== ACAuto ==== //
int n, sz=0;
char str[M];
int ch[M][N], fail[M];
queue<int> q;
int ACend[M];

inline void ACbuild() {
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) {
		scanf("%s", str);
		int p = 0;
		for (int j=0; str[j]; ++j) {
			int c = str[j]-'a';
			if(!ch[p][c]) ch[p][c]=++sz;
			p=ch[p][c];
		}
		ACend[i] = p;
	}
	for (int c=0; c<26; ++c)
		if(ch[0][c]) q.push(ch[0][c]);
	while(!q.empty()) {
		int top=q.front(); q.pop();
		for (int c=0; c<26; ++c) {
			if(!ch[top][c]) ch[top][c] = ch[fail[top]][c];
			else q.push(ch[top][c]), fail[ch[top][c]] = ch[fail[top]][c];
		}
	}
//	printf("sz = %d\n", sz);
	for (int i=1; i<=sz; ++i) adde(i, fail[i]);
	dep[0] = 1;
	dfs(0, -1);
}
// ==== LCA ==== //
namespace LCA {
	int seq[M<<1], pos[M], a[M<<2], Max, DFN=0;
	inline void build(int x, int fa) {
		pos[x] = ++DFN;
		seq[DFN] = x;
		for (int i=head[x]; i; i=next[i]) {
			if(to[i] == fa) continue;
			build(to[i], x);
			seq[++DFN] = x;
		}
	}
	inline int Min(int x, int y) {
		if(x == -1 || y == -1) return x == -1 ? y : x;
		return dep[x]<dep[y]?x:y;
	}
	inline int ask(int tl, int tr) {
		int ret = -1;
		for (tl+=Max-1, tr+=Max+1; tl^tr^1; tl>>=1, tr>>=1) {
			if(~tl&1) ret = Min(ret, a[tl^1]);
			if(tr&1) ret = Min(ret, a[tr^1]);
		}
		return ret;
	}
	inline void init() {
		build(0, -1);
		for (Max=1; Max<=DFN+1; Max<<=1);
		memset(a, -1, sizeof(a));
		for (int i=1; i<=DFN; ++i) a[Max+i] = seq[i];
		for (int i=Max-1; i>=1; --i) a[i] = Min(a[i<<1], a[i<<1|1]);
	}
	inline int lca(int x, int y) {
		x=pos[x], y=pos[y];
		if(x>y) swap(x, y);
		return ask(x, y); 
	}
}

namespace BIT {
	int c[M];
	inline int lb(int x) {
		return x&(-x);
	}
	inline void init() {
		memset(c, 0, sizeof(c));
	}
	inline void change(int x, int d) {
		for (; x<=sz+1; x+=lb(x)) c[x]+=d;
	}
	inline int ask(int x) {
		int ret=0;
		for (; x; x-=lb(x)) ret+=c[x];
		return ret;
	}
	inline int ask(int l, int r) {
		return ask(r)-ask(l-1);
	}
}

int s[M], sn=0;
inline int cmp(int x, int y) {
	return in[x]<in[y];
}

int main() {
	ACbuild();
	LCA::init();
	BIT::init();
	int T; scanf("%d", &T);
	while(T--) {
		int opt; scanf("%d", &opt);
		if(opt==1) {
			scanf("%s", str);
			int p=0; sn=0;
			for (int j=0; str[j]; ++j) {
				int c=str[j]-'a';
				while(p && !ch[p][c]) p = fail[p];
				p=ch[p][c];
				if(p) s[++sn]=p;
			}
			sort(s+1, s+sn+1, cmp);
			for (int i=1; i<=sn; ++i) BIT::change(in[s[i]], 1);
			for (int i=1; i<sn; ++i) BIT::change(in[LCA::lca(s[i], s[i+1])], -1);	
		} else {
			int x; scanf("%d", &x);
			printf("%d\n", BIT::ask(in[ACend[x]], out[ACend[x]]));
		}
	}
	
	return 0;
}

那么从这题我们能得出什么启示呢?

仔细阅读题目,然后得出结论(要在fail树上干什么)

然后习惯性联想DFS序寻找解决办法。

适当运用数据结构简化复杂度。

哦本题复杂度忘记分析啦!

令$all~in~S=|S|, all~in~T=|T|$,复杂度即为$O(|S|log|S|+|T|log|T|)$

Canara Internet Bank 说:
2022年8月06日 22:13

Canara Bank has been providing service to their customers since 1906 and in this meantime it has seen great growth, and the banking network in modern technology and providing easy services to every customer in their footsteps has emerged with great technology growth. Canara Internet Banking Login Canara bank net banking service by giving various options to the customer which enables them not to walk to the branch office to use every option.Bank as well got their branch setup virtually with having multiple customer support assistance which ensure that their customer account creates online and as well get used to other services.

Kerala SSLC importa 说:
2023年9月14日 19:32

Kerala SSLC Blueprint 2024 are designed According to the Latest Exam Pattern for English, Biology, Mathematics, Physics, Chemistry, Social Science, Third Language Hindi, Malayalam Subject Wise Important Question Prepare by Senior Experts, so it will help Students to know the Exact Difficulty level of the Kerala SSLC Question Paper 2024 we have Provided All the Subjects can Download the Exam Kerala SSLC important Questions Paper 2024 Papers very easily.Students, who’re starting their Preparation for Kerala General Education Examination, they can easily get idea about which type of question will be asked in SSLC Exam, then Start Your Preparation with Kerala SSLC Mock Test Paper 2024 Download will also help them on how to time each Question


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter