BZOJ 3881: [Coci2015]Divljak [AC自动机 树链的并]

3881: [Coci2015]Divljak

题意：添加新文本串，询问某个模式串在多少种文本串里出现过

---

模式串建AC自动机，考虑添加一个文本串，走到的节点记录下来求树链的并

方法是按dfs序排序去重，每个点+1，相邻点lca-1

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=4e6+5;

inline int read(){

    char c=getchar();int x=0,f=1;

    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

    return x*f;

}

int n, Q, op, x;

char s[N];

struct edge {int v, ne;} e[N];

int cnt=1, h[N];

inline void ins(int u, int v) {//printf("ins %d %d\n",u,v);

e[++cnt]=(edge){v, h[u]}; h[u]=cnt;}

namespace ac{

	struct meow{int ch[26], fail, val;} t[N];

	int pos[N], sz;

	void insert(char *s, int id) {

		int len = strlen(s+1), u=0;

		for(int i=1; i<=len; i++) {

			int c=s[i]-'a';

			if(!t[u].ch[c]) t[u].ch[c] = ++sz;

			u=t[u].ch[c];

		}

		pos[id]=u;

	}

	int q[N], head, tail;

	void build() {

		head=tail=1;

		for(int i=0; i<26; i++) if(t[0].ch[i]) q[tail++] = t[0].ch[i];

		while(head != tail) {

			int u=q[head++];

			for(int i=0; i<26; i++) {

				int &v = t[u].ch[i];

				if(!v) v = t[t[u].fail].ch[i];

				else t[v].fail = t[t[u].fail].ch[i], q[tail++]=v;

			}

		}

		for(int i=1; i<=sz; i++) ins(t[i].fail+1, i+1);

	}

}using ac::t; using ac::sz;

int L[N], R[N], dfc, mx[N], deep[N], size[N], fa[N], top[N];

void dfs(int u) {

	size[u]=1;

	for(int i=h[u];i;i=e[i].ne) {

		int v=e[i].v;

		fa[v]=u; deep[v]=deep[u]+1;

		dfs(v);

		size[u]+=size[v];

		if(size[v] > size[mx[u]]) mx[u]=v;

	}

}

void dfs(int u, int anc) {

	L[u] = ++dfc;

	top[u] = anc;

	if(mx[u]) dfs(mx[u], anc);

	for(int i=h[u];i;i=e[i].ne) if(e[i].v != mx[u]) dfs(e[i].v, e[i].v);

	R[u] = dfc;

}

int lca(int x, int y) {

	while(top[x] != top[y]) {

		if(deep[top[x]] < deep[top[y]]) swap(x, y);

		x = fa[top[x]];

	}

	return deep[x] < deep[y] ? x : y;

}

int c[N];

inline void add(int p, int d) { //printf("add %d  %d\n",p,d);

	if(p==0) puts("nooo");

	for(; p<=sz+1; p+=p&-p) c[p]+=d;}

inline int sum(int p) { //printf("sum %d\n",p);

	if(p==-1) puts("nooo");

	int ans=0; for(; p; p-=p&-p) ans+=c[p]; return ans;}

int a[N];

inline bool cmp(int x, int y) {return L[x]<L[y];}

void solve(char *s) { //printf("solve %s\n",s+1);

	int len=strlen(s+1), u=0, p=0;

	for(int i=1; i<=len; i++) {

		u=t[u].ch[s[i]-'a'];

		a[++p]=u+1;

	}

	sort(a+1, a+1+p, cmp); p = unique(a+1, a+1+p) - a - 1;

	for(int i=1; i<=p; i++) {

		add(L[a[i]], 1);

		if(i!=1) add(L[ lca(a[i], a[i-1]) ], -1);

	}

}

int que(int x) { //printf("que %d\n",x);

	return sum(R[x]) - sum(L[x]-1);

}

int main() {

	freopen("in","r",stdin);

	n=read();

	for(int i=1; i<=n; i++) scanf("%s",s+1), ac::insert(s, i);

	ac::build();

	dfs(1); dfs(1, 1); //puts("hi");

	//for(int i=1; i<=sz+1; i++) printf("LR %d  %d %d\n", i, L[i], R[i]);

	Q=read();

	for(int i=1; i<=Q; i++) {

		op=read();

		if(op==1) scanf("%s",s+1), solve(s);

		else printf("%d\n", que(ac::pos[read()]+1));

	}

}