CodeForces 547E Mike and Friends (AC自动机,BIT)

给出n个字符串,计算字符串k在[l, r]的字符串中总共出现多少次。

首先我们将这n个字符串插入到AC自动机中,构造出fail树,于是乎我们就可以dfs出fail树的dfs序,这样我们用BIT维护一颗子树的信息,对于每个询问我们将l, r分别存下来离线处理,然后从第一个字符串开始对BIT维护的fail树节点进行跟新,那么我们就可以对某个询问的[1, l-  1]或者[1, r]求出一k为根的子树节点的权值和,每个节点的权值表示次节点目前为止出现的次数。如果强制在线的话,可以用主席树搞过。

 

LEAVE A COMMENT