Category Archives: AC自动机

HDU 4117 GRE Words (AC自动机,dp,线段树)

给出n个字符串,以及格子的权值,按照顺序取出若干个字符串,要去前一个字符串是后一个字符串的子串。计算最大权值和 …

UVALive 6495 (AC自动机,高斯消元)

一个硬币,正面用T表示反面用H表示,现在两个人各自猜了一个长度是L的序列,序列每个元素表示正面还是反面,现在硬 …

2016 ACM/ICPC Asia Regional Qingdao Online

1001 – I Count Two Three 水题,大表+二分即可 1002 –  …

CodeForces 86C Genetic engineering (AC自动机,dp)

给出n (n <= 1000) 个字符串,构造一个长度是L的字符串,这L长的字符串是由n个字符串拼接而成 …

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

给出n个字符串,计算字符串k在[l, r]的字符串中总共出现多少次。 首先我们将这n个字符串插入到AC自动机中 …

Codeforces Round #362 (Div. 1)

A – Lorenzo Von Matterhorn 给出n个点的树(n <=1e18),i …

SPOJ 7758 Growing Strings (AC自动机)

给出n个串,选出若干个串排成一行,保证前一个是后一个的前缀或者后缀,求最多能选出多少个串满足条件。 公共前缀其 …

HDU 5566 Clarke and room (树链剖分,线段树,ac自动机)

给出一棵树,树上每个节点有一个名字字符串,有q个询问,计算树链u-v经过的点对应的字符串是si的子串的最大长度 …

AC自动机

ac自动机是kmp的高级版,实现多模式串匹配,常常伴有dp计数即动态转移图 [crayon-5bc9608dd …