CF710F String Set Queries

AC自动机好题

删除的答案其实很好统计qwq,我们先查询在删除自动机里面的答案,再查询在全体自动机的答案

然后做一个差就是答案....

不过我们AC自动机这个东西没法边着插入边维护fail树QAQ

所以我们肯定要用一些定期重构之类的想法去维护AC自动机

根号分块是肯定可以的,就是每根号m的开一个自动机,如果不到根号m个没有存入可以直接暴力匹配

(当然也最推荐写这个)

然而复杂度不好看,我们有一个log的做法...

二进制分组....

假设现在有n个,n的第k位为 $a_i$ 就存储 $2^a_i$ 个串构成

然后查询的时候暴力把log个自动机都跑一遍

修改n的时候进位我们就把那些都暴力重构组成一个新的自动机放在新的二进制位上

由于一个串最多重构log次所以是对的

这样子我们只需要把一些AC自动机中的串拿出来重构

具体实现的时候我们对于每个二进制位都弄一个链表记录该位存储的哪些串就行了

这个二进制分组的思想好像也仅适用于这类数据结构的情况?

有一个大大的细节就是清空ch树的时候要延迟清空.....具体可看看代码实现

code:


//二进制分组
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 7;
char s[MAXN];

struct ACF {//ACFUN
	string data[MAXN];
	int ch[MAXN][26], fail[MAXN], ed[MAXN], T, n;
	inline void ins(int r, char *s) {
		int n = strlen(s + 1);
		int u = r;
		for(int i = 1, t; i <= n; ++i) {
			t = s[i] - 'a';
			if(ch[u][t] == r) {//要把这个点重构然后再把其他的重构
				ch[u][t] = ++T;
				for(int j = 0; j < 26; ++j)
					ch[T][j] = r;
			}
			u = ch[u][t];
		}
		ed[u]++;
	}
	void build(int r) {
		fail[r] = r;
		queue<int> q;
		for(int i = 0; i < 26; ++i) {
			if(ch[r][i] > r) {
				q.push(ch[r][i]);
				fail[ch[r][i]] = r;
				//fail....
			}
		}
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			for(int i = 0; i < 26; ++i) {
				int v = ch[u][i];
				if(v == r)
					ch[u][i] = ch[fail[u]][i];
				else {
					fail[v] = ch[fail[u]][i];
					ed[v] += ed[ch[fail[u]][i]];
					q.push(v);//fail重构
				}
			}
		}
	}
	int search(int r, char *s) {
		int n = strlen(s + 1);
		int u = r;
		int ret = 0;
		for(int i = 1, t; i <= n; ++i) {
			t = s[i] - 'a';
			u = ch[u][t];
			ret += ed[u];
		}
		return ret;
	}
	int stk[MAXN], fr[MAXN], siz[MAXN], N;
	void merge() {
		--N;
		siz[N] <<= 1;
		for(int i = stk[N]; i <= T; ++i) {
			ed[i] = fail[i] = 0;
			for(int j = 0; j < 26; ++j) {
				ch[i][j] = 0;
			}
		}
		T = stk[N];
		for(int i = 0; i < 26; ++i)
			ch[T][i] = T;
		for(int L = fr[N]; L <= n; ++L)
			ins(stk[N], &data[L][0]);
		build(stk[N]);
	}
	void ins(char *s) {
		stk[++N] = ++T;
		for(int i = 0; i < 26; ++i)
			ch[T][i] = T;
		siz[N] = 1;
		ins(T, s);
		build(stk[N]);
		int L = strlen(s + 1);
		data[fr[N] = ++n] = " ";
		for(int i = 1; i <= L; ++i)
			data[n] += s[i];
		while(siz[N] == siz[N - 1])
			merge();
	}
	int Count(char *s) {
		int ans = 0;
		for(int i = 1; i <= N; ++i)
			ans += search(stk[i], s);
		return ans;
	}
} Add, Sub;

int m;
int main() {
	scanf("%d", &m);
	for(int i = 1, typ; i <= m; ++i) {
		scanf("%d", &typ);
		cin >> (s + 1);
		if(typ == 1) {
			Add.ins(s);
		} else if(typ == 2) {
			Sub.ins(s);
		} else {
			printf("%d\n", Add.Count(s) - Sub.Count(s));//做差即可
		}
		fflush(stdout);
	}
	return 0;
}

夏晓光(loveJY)的博客

P4198 楼房重建