bzoj 3238 差异

题目传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=3238 后缀数组+单调队列 这是一道后缀数组的模板题。 简单来说,就是先用后缀数组求出h数组。 然后利用单调队列在o(n)的时间复杂度下求出任意两个后缀的最大公共前缀长度的和。 大家看代码 …

回文自动机Palindromic Automaton(又称回文树Palindromic Tree,简称pam)能干什么? 对于字符串S[1..n],比如它可以求出S的所有本质不同的回文子串,并求出每一个本质不同的子串在S中出现的次数,当然还能干别的很多事情。 现在来看回文自动机是如何构建的。 定义变 …

题目传送门 先来考虑如何快速的求出一个子串的出现次数,那就建一个后缀自动机,预处理出每一个节点的|right(x)|,然后找到子串对应的节点就好了。但是如果从root开始转移的话太慢了,而且不好优化,所以可以尝试倒着来。在建sam的时候顺便记录s[1..x]所对应的节点,对于子串s[l..r],其所 …

题目传送门 看到题目描述的最后一句话,意思是这棵树最多只有20个叶子节点,这个限制很奇怪,也是本题的突破口。考虑任意一条链组成的字符串,不难发现都会被起点为某一个叶子的字符串包含。由于叶子节点的个数非常少,所以可以将以这些节点为起点的路径组成的字符串全部加入到一个广义后缀自动机里,然后就可以直接统计 …

我能表示自己不会做吗。 好吧。 其实这道题就是个裸的KMP 但我一开始竟然没有看出来 显而易见的是,如果要添加几个字符的话,肯定是字符串的循环节缺了一部分 所以答案是 (n-fail[n])-n%(n-fail[n]) Code: #include<cstdio> #include …

这道就是纯KMP,QAQ。 你只要把这两个字符串合在一起求一遍KMP就可以了 注意最后输出的总长度必须小于等于min(len1,len2). Code: #include<cstdio> #include<cstring> #include<algorithm> …

继续切水题的我。 这道题算法KMP 然后你只需要在做KMP的时候看一下i%(i-next[i])是否等于0且next[i]不为0 如果是0说明这里有循环节(不信你可以自己模拟一下QAQ) Code: #include<cstdio> #include<algorithm> u …

感觉最近只有我在写博客啊。 这道题的方法是AC自动机+dfs序+树状数组。 你扫描字符串,遇到‘P’就把当前节点设为危险节点,遇到‘B’就返回它的父亲,否则正常转移 于是一个AC自动机就建出来了。 然后你就是跑出以fail数组为连边的树的DFS 离线操作,将询问按y排序, 再次扫描字符串 如果为P, …

这是一道AC自动机QAQ. 题意是求任意两个字符串前缀的最大公共后缀,并且这个后缀要在一个字符串里出现过,输出这个后缀转化成十进制后的答案。 显而易见的是,先建个AC自动机,然后求出fail数组。 你的问题其实就是求两个字符串前缀所在的节点的LCA,然后输出根到它路径上所形成的字符串即可(这个可以预 …

这道可以用KMP 很显然又是一个模板题 只不过因为n太大了,于是用了矩阵乘法 你只要先预处理出fail数组, 然后转移矩阵也就可以求出来了, 你只需要枚举每个前缀的转移,假设枚举前缀i,有一个转移是j,你就在g[i][j]上+1 不过注意如果转移为m的话就continue 代码还是很短。 Code: …