AC自动机练习

多模板串匹配一般有两种方法

暴力kmp, 适用于模板串少的情形
直接trie上暴力, 适用于模板串比较短的情形, 并且可以动态插入合并
建立AC自动机, 复杂度是严格线性的, 但不能动态插入

const int N = 1e6+10;
int n, tot, T, ok;
int val[N], fa[155], ch[N][26], cnt[155];
char p[155][80], s[N];

int newnode() {
	val[++tot]=0,memset(ch[tot],0,sizeof ch[tot]);
	return tot;
}
void ins(int &o, char *s, int id) {
	if (!o) o=newnode();
	if (!s[0]) return val[o]?fa[id]=val[o]:val[o]=id,void();
	ins(ch[o][s[0]-'a'],s+1,id);
}
void find(int o, char *s) {
	if (!o) return;
	++cnt[val[o]];
	if (s[0]) find(ch[o][s[0]-'a'],s+1);
}
void work() {
	REP(i,1,n) scanf("%s", p[i]),ins(T,p[i],i);
	scanf("%s", s);
	for (char *t=s; *t; ++t) find(T,t);
	int ans = *max_element(cnt+1,cnt+1+n);
	printf("%d\n", ans);
	REP(i,1,n) if (cnt[fa[i]]==ans) puts(p[i]);
}

练习1. CF 710F String Set Queries

大意: 要求维护一个集合, 可以实现 1.插入一个串S 2.删除一个串S 3.给出一个串S, 询问集合中所有串在S中出现的次数.

维护插入删除两种ac自动机最后相减即可, 但是因为ac自动机不支持动态插入, 要实现插入只能暴力重建. 可以将trie二进制分组合并之后再重建, 这样最后建立的ac自动机总个数是$O(logn)$, 复杂度就为$O(nlogn)$

这题还可以直接分块做, 大于$\sqrt{N}$的用kmp匹配, 其余直接建trie暴力匹配, 复杂度是$O(n\sqrt{n})$

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef pair<int,char> pii;

const int N = 3e5+10, M = 600;
int n, tot, T = ++tot, len;
int val[N], f[N], ch[N][26], q[700];
char s[N];
pii fa[N];
void ins(int o, char *s, int v, int d) {
    if (!s[0]) { 
		val[o] += v;
		if (d>M) q[++*q]=o;
		return;
	}
	int &p = ch[o][s[0]-'a'];
	if (!p) p=++tot;
	fa[p]=pii(o,s[0]), ins(p,s+1,v,d+1);
}
int find(int o, char *s, int d) {
    if (!o||d>M) return 0;
    return val[o]+(s[0]?find(ch[o][s[0]-'a'],s+1,d+1):0);
}
char p[N];
int kmp(int o) {
	int m = 0;
	while (o) p[m++]=fa[o].second, o=fa[o].first;
	--m;
	reverse(p,p+m);
	int j = 0, r = 0;
	REP(i,1,m-1) {
		while (j&&p[j]!=p[i]) j=f[j];
		if (p[j]==p[i]) ++j;
		f[i+1]=j;
	}
	j = 0;
	REP(i,0,len-1) {
		while (j&&p[j]!=s[i]) j=f[j];
		if (p[j]==s[i]) ++j;
		if (j==m) ++r;
	}
	return r;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int op;
		scanf("%d%s", &op, s);
		if (op==3) { 
			len = strlen(s);
			int ans = 0;
			REP(i,0,len-1) ans+=find(T,s+i,0);
			REP(i,1,*q) if (val[q[i]]) {
				ans += val[q[i]]*kmp(q[i]);
			}
			printf("%d\n", ans);
			fflush(stdout);
		}
		else ins(T,s,op==1?1:-1,0);
	}
}

相关文章