夜间模式暗黑模式
字体
阴影
滤镜
圆角

月份:2017年9月

篇文章

后缀自动机
因为我知道后缀自动机的构造是比较难以理解的,所以我想先知道后缀自动机构建出来的东西是什么。 首先后缀自动机构造出来的一定是一个自动机,这个自动机可以接收一个字符串所有的后缀,显然这个自动机是一个DAG图。 然后这个自动机的每个状态代表什么呢?代表结束位置相同的子串,比如ab和aab在aabaab中都在\(3,6\)位置结尾,那么这两个串可以认为在后…
虚树
其实虚树这一套没什么,就是一个板子。主要解决的是给一个树,然后对树上的某个点集搞些什么操作啊询问啊,之类的问题。 就是把原树的dfs序搞出来,然后把要搞的点和lca拿出来,搞一棵新的树,用单调栈来时限,其实就是一个模板。 例题是bzoj 3611 给定一棵树,然后询问一个点集的所有互相之间的路径和以及最长路径最短路径 把虚树建出来,然后就树dp随便…
Shift-and 算法
去年大连的一个题目,当时现场赛的时候就没做出来。赛后出题人说是“经典”的shift-and算法(经典个jb啊?),不过到现在才补,也是挺菜的。 例题是hdu 5972 给一个长度为n的模式子串,子串的每个位置分别可以是一些数字,即一个位置可以被多个数字匹配。再给定一个母串,问子串可以在哪些位置和木串匹配,并且输出匹配成功后的所有子串。 这个shif…