icontofig | 发布于 2019-09-22 21:13:56 | 阅读量 392 | 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 | 阅读量 385 | 字符串 可持久化线段树
发布于 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 | 阅读量 426 | 字符串
发布于 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 | 阅读量 274 | 字符串 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 | 阅读量 297 | 字符串 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
继续阅读