louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共2篇）

AC自动机

简单地说，AC自动机就是可以匹配好多字符串的东西。。。。其实就是在Trie树上做KMP。fail[i]表示的是i节点代表的串的意义就是在Trie上出现过的最长后缀（当然不包括自己）所在的节点。如果暴力找fail[i]的话会超级慢，所以我们可以把值为0的tr[i][j]赋为tr[fail[i]][j]...

字符串 AC自动机

2020-05-10

0 836

题解 | 信息学奥赛一本通 GT考试

思路先不考虑数据范围,我们设表示当前构造到第位,已经匹配了位的方案数.最终答案即为我们可以写出一个递推式,是我们要求的系数.我们可以使用KMP来求系数.只要求出前位(长度为)与相同,下一位的数字为时,与最大的匹配长度.对于每一个,,很明显不能承受.但是系数每次转移都不会变,因此直接用矩阵快速幂优化...

字符串矩阵乘法快速幂 KMP

2019-08-24

0 556