青竹qingzhu

AC自动机

KMP(3) tarjan(2) 主席树(2) 二分(1) 优先队列(1) 倍增(2) 后缀数组(1) 后缀自动机(1) 图论(1) 技巧(3) 最短路(10) 树状数组(1) 线性基(3) 网络流(10) 题解(7)

/ 注册

全部文章 / AC自动机（共3篇）

Poj1625 AC自动机+大数+DP

poj1625 题意给一个含n个字符的字符集，p个字符串，问长度为m的字符串有多少种不包含任意一个字符串pi。题解首先这题应该想到dp，dp[i][j]表示长度为i的字符串以节点j（节点j表示一个AC自动机上的一个状态节点）结尾的满足条件的字符串种类。以p个字符串建立AC自动机，标记危险节点。...

2020-07-13

0 612

hdu3341AC自动机+变进制状压dp

hdu3341 题意给m个模式串和一个母串（字符串都是由ATCG组成），求这个母串重组后最多包含多少个模式串，可以重叠。思路看题目数据范围很小，首先暴力的思想，把母串的所有可能的排列方式都求一遍，取最大值。建立模式串的AC自动机，dp[i][x1][x2][x3][x4]表示i状态下有x1个A...

2020-07-13

0 437

hdu4511 AC自动机+最短路dp

题目链接题意直角坐标系中n个点，限制一些走过的路径的顶点顺序，要求从1到n最短的距离。如：不能经过1 -> 2 -> 3，那么就要求走过的路径不能包含有1 -> 2 -> 3这部分，但是1 -> 3 或者1 -> 2都是可以的，这样的限制路径可能有多条。思路...

2020-07-13

0 451