后缀自动机

因为我知道后缀自动机的构造是比较难以理解的,所以我想先知道后缀自动机构建出来的东西是什么。 首先后缀自动机构造出来的一定是一个自动机,这个自动机可以接收一个字符串所有的后缀,显然这个自动机是一个DAG图。 然后这个自动机的每个状态代表什么呢 … 继续阅读 后缀自动机

虚树

其实虚树这一套没什么,就是一个板子。主要解决的是给一个树,然后对树上的某个点集搞些什么操作啊询问啊,之类的问题。 就是把原树的dfs序搞出来,然后把要搞的点和lca拿出来,搞一棵新的树,用单调栈来时限,其实就是一个模板。 例题是bzoj 3 … 继续阅读 虚树