icontofig | 发布于 2020-02-19 22:10:38 | 阅读量 989 | 字符串 可持久化线段树 可持久化数据结构 Trie
Codeforces 547E Mike and Friends AC自动机Fail树上DFS序建可持久化线段树
Input5 5 a ab abab ababab b 1 5 1 3 5 1 1 5 2 1 5 3 1 4 5Output7 5 6 3 6题目大意给出n个字符串,q次询问,每次询问l,r,k,求问 字符串l——r中,包含字符串k(字符串k作为子串)的字符串个数是多少。 题解多模式串匹配肯定是AC自动机 但是这个问题是多个串中有多少能匹配到当前询问的这一个字串的问题,而不是经典的某个串能匹配多少个已经给出的串的问题。 AC自动机的Trie树中,某个节点的所有祖先节点表示一个或几个字符串在当前这个位置之前的字符串前缀。所以对于某个结束节点来说,他的所有祖先节点加上他本身构成了一个字符串。 而
继续阅读
icontofig | 发布于 2020-02-12 22:36:15 | 阅读量 344 | 字符串
发布于 2020-02-12 22:36:15 | 字符串
CodeForces 710F. String Set Queries 模拟二进制堆启发式合并的AC自动机合并
题目大意维护一个集合支持: 1." data-mce-tabindex="0">1.1. 添加一个模式串。 2." data-mce-tabindex="0">2.2. 删除一个串。 3." data-mce-tabindex="0">3.3. 给出一个串,询问有多少个子串在集合中出现过,多次出现多次计算。 题目要求使用fflush(stdout)方法强制在线。 题解更新了AC自动机内存池回收写法的模板。 多模式串匹配算法,明显的AC自动机的题目。 但是众所周知,AC自动机不支持动态的插入操作以及删除操作(Trie树是支持动态插入的,但是AC自动
继续阅读
icontofig | 发布于 2020-01-27 16:34:36 | 阅读量 633 | 字符串
发布于 2020-01-27 16:34:36 | 字符串
#include <bits/stdc++.h> const int maxn = 2e5 + 5; using namespace std; struct Trie{ int nex[maxn][26], fail[maxn], end[maxn]; int root, p; inline int newnode() { for (int i = 0; i < 26; ++i) { nex[p][i] = -1; } end[p++] = 0; return p
继续阅读
icontofig | 发布于 2020-01-14 18:21:16 | 阅读量 758 | DP 字符串
发布于 2020-01-14 18:21:16 | DP 字符串
HDU 2457 DNA Repair AC自动机 DP
题目大意给出n个模式串和一个匹配串,求问最少要修改匹配串中多少个字符才能使得匹配串中不含有任意一个模式串。 题解多个模式串一定要用AC自动机的 所以首先把AC自动机给建出来 然后在AC自动机上跑DP,dp[i][j]表示当前匹配到长度为i,在AC自动机的Trie树上走到节点j的状态下的所需要修改的字符数量的最小值。 要注意不能走到模式串结尾的节点上。 在转移的时候,从当前状态向其子节点转移(前提是子节点非模式串结束的位置对应的节点),如果转移的节点的字符与字符串下一个字符相同,那么下一个状态的dp值继承当前状态dp值,代表不修改下一个字符的情况;否则下一个状态的dp值要在当前状态的dp值的基础
继续阅读
icontofig | 发布于 2019-09-22 21:13:56 | 阅读量 476 | FFT 字符串 生成函数
发布于 2019-09-22 21:13:56 | FFT 字符串 生成函数
BZOJ 3160 万径人踪灭 FFT + 回文自动机 + 生成函数
题目大意 给定一个字符集仅含a和b的字符串s,求字符串中不连续的回文子序列个数mod 1000000007的值。 题解如果是连续的回文子序列,也就是回文串,那就很好求了,直接运用Manacher算法就可以了。 但是这题是让算所有的不连续的回文子序列…… 然而这个是没法直接算出来的…… 所以我们反过来想,我们可以把所有回文子序列的数量求出来,然后减去回文子串的数量,就是不连续的回文子序列的数量。 上面说了,如果是回文子串的数量,可以直接用Manacher算法算出来。 所以现在我们考虑的就是全体回文子序列的数量该怎么算。 对一个回文子序列,一定有一个中心,假设两个对应字符位置分别为x,y
继续阅读
icontofig | 发布于 2019-09-11 08:47:43 | 阅读量 495 | 字符串 可持久化线段树
发布于 2019-09-11 08:47:43 | 字符串 可持久化线段树
The Preliminary Contest for ICPC Asia Xuzhou 2019 G.Colorful String PAM(回文自动机) + 可持久化线段树
题目大意给出一个字符串,求出所有回文串的字符种类数之和。 题解考场上他们都有回文自动机的板子而我没有QAQ 首先对于一个子串,其对应一个子区间,这个子区间的数据的种类数的多少我们是可以用主席树来维护的,这是众所周知的。 具体维护方法: 从第1位置往后扫,如果之前出现过相同的数据,我们就在之前出现过的位置-1,在当前位置计数+1,然后把当前位置记录下来。 但是我们怎么求所有回文串的长度和数目?Manacher是不行的,效率太低了。 于是有一个神奇的PAM,也就是回文自动机。 回文自动机中,cnt[i]表示以i结尾的最长的回文串的数目,len[i]表示以i结尾的回文串的长度为多少,pos[i]表示
继续阅读
icontofig | 发布于 2019-08-26 00:22:58 | 阅读量 484 | 字符串
发布于 2019-08-26 00:22:58 | 字符串
//后缀数组sa[i]就表示排名为i的后缀的起始位置的下标 //而它的映射数组rk[i]就表示起始位置的下标为i的后缀的排名 //height[i]表示lcp(i,i-1),s为下标1 to len char s[maxn]; int y[maxn], x[maxn], c[maxn], sa[maxn], rk[maxn], height[maxn]; int n, m; inv get_SA() { memset(c, 0, sizeof(c)); for (int i = 1; i <= n; ++i) ++c[x[i] = s[i]]; for (int
继续阅读
icontofig | 发布于 2019-04-06 15:14:55 | 阅读量 314 | 字符串 Trie
发布于 2019-04-06 15:14:55 | 字符串 Trie
poj - IMMEDIATE DECODABILITY Trie树模板
 题解本题为Trie(字典树)的模板题。 我们先来说一下Trie的基本构造: Trie树,又名字典树,故名思义,将字符串各个字符以类似字典的方式构造成一棵树,以便检索。 Trie树的每一个节点的深度代表着当前检索到的字符串的长度。而Trie树的每两个节点之间的边可以认为是代表着字典中的一个字符。 字典树的根节点是我们检索字符串的起始,我们每次检索字符串都是由这个根节点开始的。我们每检索一个字符,就顺延着当前这个字符所代表的边走向下一个节点。 有些节点会打一个flag标记,这代表着Trie树中一个单词的结束。 以上是Trie树的基本构造。 对于这个题目,它的要求是判断任意一个字符串不能
继续阅读
icontofig | 发布于 2019-04-05 22:47:29 | 阅读量 332 | 字符串 KMP
发布于 2019-04-05 22:47:29 | 字符串 KMP
    不解释,就是KMP模板题……给出个人常用KMP模板QAQ #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <string> #include <cstring> #include <cmath> using namespace std; string s1; s
继续阅读