uniHk

后缀自动机

01Trie(5) AC自动机(7) CDQ分治(4) dsu on tree(1) K-D Tree(5) 主席树(5) 各类说明(1) 后缀数组(1) 回文自动机(6) 字符串（杂）(6) 康托展开(1) 数学(7) 整体二分(1) 斜率优化DP(3) 树链剖分(3) 概率DP(2) 算法(Lazy)(38) 线性基(5) 莫队(6) 计算几何(3)

/ 注册

全部文章 / 后缀自动机（共11篇）

洛谷-P3975 弦论(后缀自动机板子题)

弦论一道板子题，让我感觉板子题都还不会。。。然后把递推写成dfs时没有给string加上&，导致内存爆了，2333，果然还是传引用好题意：求字典序第K小子串以及本质不同的第K小子串思路：正常的建好后缀自动机由于处理一个节点有多少endpos以及经过一个节点有多少子...

2020-01-02

0 850

后缀自动机

最最详细的解析基础学习简洁明了的讲解小小总结总状态数不超过 2 n − ...

2020-01-02

0 354

洛谷-P3804 后缀自动机板子题

后缀自动机板子题题意：给了一个字符串，然后里面有些子串出现次数大于1，求这种子串的出现次数乘以子串长度的最大值。思路：正常建好后缀自动机，将所有的np节点出现次数赋值为1 记录所有的父节点有几个儿子(不是后缀自动机上的儿子数，而是parent tree上的儿子数) 利用to...

2020-01-02

0 636

找相同字符(后缀自动机)

找相同字符题意：给定两个字符串，在两个字符串中任选子串，求两子串相同的方案数思路：用后缀自动机处理两个字符串，一般考虑在中间插入一个用不到的字符（比如’#’），然后将它们组成一个串(后来发现好像不能插’#’，毕竟我数组第二维只开了26的大小；然后有一个方法就是把数组开成27的，然后...

2020-01-02

0 732

洛谷 P-2178 品酒大会(后缀自动机)

品酒大会又一道黑题！以为自己 O ( n ) ...

2020-01-02

0 603

Megumi With String（2019南昌网络赛F）（后缀自动机+数学期望）

Megumi With String 这题我T了40次左右。。。拿着别人的AC代码双向修改，我的一直T，别人的一直A。。。甚至感觉除了变量名不一样，其他的都完全一样了，还是T 噩梦经历最后发现是初始化函数写跪了题意：给定一个已知串 ...

2020-01-02

0 492

Can You Solve the Harder Problem?（2018ICPC焦作H）（后缀自动机+单调栈）

Can You Solve the Harder Problem? 这题简直妙呀！可惜训练赛的时候 3 h ...

2020-01-02

0 568

熟悉的文章（后缀自动机+二分答案+单调队列）

熟悉的文章题意：给定一本包含 M M M个字符串（ 01 ...

2020-01-02

0 472

喵星球上的点名（后缀自动机+dfs序+莫队）

喵星球上的点名一道据传言有多种解法的题（不过大多是因为数据太弱过的）。先用AC自动机搞了一上午，无果；看了题解，后缀自动机+莫队？正好是我最喜欢的算法之一+正在学习的算法，就这个了！然后由于广义自动机的 l ...

2020-01-02

0 460

最短不公共子串（后缀自动机+序列自动机+bfs）

最短不公共子串题意：问最短的满足：是A的子串（子序列），且不是B的子串（子序列，子序列（子串））。（共四个问题）思路：子串问题，考虑后缀自动机；子序列问题，考虑序列自动机；这不就成板子题了？然后本题要求属于前者，而不属于后者的子结构，可以考虑暴力的在两种DAG上同时跑；若...

2020-01-02

0 463