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));
}
}
上一篇:一台电脑存放多个git账户的多个rsa秘钥


下一篇:scrapy之Crawspider 腾讯招聘实战案例