uniHk
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)
归档
标签
去牛客网
登录
/
注册
uniHk的博客
Universe of Hawking
全部文章
/ 后缀自动机
(共11篇)
洛谷-P3975 弦论(后缀自动机板子题)
弦论 一道板子题,让我感觉板子题都还不会。。。然后把递推写成dfs时没有给string加上&,导致内存爆了,2333,果然还是传引用好 题意:求字典序第K小子串以及本质不同的第K小子串 思路: 正常的建好后缀自动机 由于处理一个节点有多少endpos以及经过一个节点有多少子...
2020-01-02
0
847
后缀自动机
最最详细的解析 基础学习 简洁明了的讲解 小小总结 总状态数不超过 2 n − ...
2020-01-02
0
353
洛谷-P3804 后缀自动机板子题
后缀自动机板子题 题意:给了一个字符串,然后里面有些子串出现次数大于1,求这种子串的出现次数乘以子串长度的最大值。 思路: 正常建好后缀自动机,将所有的np节点出现次数赋值为1 记录所有的父节点有几个儿子(不是后缀自动机上的儿子数,而是parent tree上的儿子数) 利用to...
2020-01-02
0
630
找相同字符(后缀自动机)
找相同字符 题意:给定两个字符串,在两个字符串中任选子串,求两子串相同的方案数 思路: 用后缀自动机处理两个字符串,一般考虑在中间插入一个用不到的字符(比如’#’),然后将它们组成一个串(后来发现好像不能插’#’,毕竟我数组第二维只开了26的大小;然后有一个方法就是把数组开成27的,然后...
2020-01-02
0
726
洛谷 P-2178 品酒大会(后缀自动机)
品酒大会 又一道黑题!以为自己 O ( n ) ...
2020-01-02
0
600
Megumi With String(2019南昌网络赛F)(后缀自动机+数学期望)
Megumi With String 这题我T了40次左右。。。拿着别人的AC代码双向修改,我的一直T,别人的一直A。。。甚至感觉除了变量名不一样,其他的都完全一样了,还是T 噩梦经历 最后发现是初始化函数写跪了 题意:给定一个已知串 ...
2020-01-02
0
491
Can You Solve the Harder Problem?(2018ICPC焦作H)(后缀自动机+单调栈)
Can You Solve the Harder Problem? 这题简直妙呀!可惜训练赛的时候 3 h ...
2020-01-02
0
567
熟悉的文章(后缀自动机+二分答案+单调队列)
熟悉的文章 题意: 给定一本包含 M M M个字符串( 01 ...
2020-01-02
0
471
喵星球上的点名(后缀自动机+dfs序+莫队)
喵星球上的点名 一道据传言有多种解法的题(不过大多是因为数据太弱过的)。先用AC自动机搞了一上午,无果;看了题解,后缀自动机+莫队?正好是我最喜欢的算法之一+正在学习的算法,就这个了!然后由于广义自动机的 l ...
2020-01-02
0
459
最短不公共子串(后缀自动机+序列自动机+bfs)
最短不公共子串 题意: 问最短的满足:是A的子串(子序列),且不是B的子串(子序列,子序列(子串))。(共四个问题) 思路: 子串问题,考虑后缀自动机;子序列问题,考虑序列自动机;这不就成板子题了? 然后本题要求属于前者,而不属于后者的子结构,可以考虑暴力的在两种DAG上同时跑;若...
2020-01-02
0
461
首页
上一页
1
2
下一页
末页