题目传送门 先来考虑如何快速的求出一个子串的出现次数,那就建一个后缀自动机,预处理出每一个节点的|right(x)|,然后找到子串对应的节点就好了。但是如果从root开始转移的话太慢了,而且不好优化,所以可以尝试倒着来。在建sam的时候顺便记录s[1..x]所对应的节点,对于子串s[l..r],其所 …

题目传送门 看到题目描述的最后一句话,意思是这棵树最多只有20个叶子节点,这个限制很奇怪,也是本题的突破口。考虑任意一条链组成的字符串,不难发现都会被起点为某一个叶子的字符串包含。由于叶子节点的个数非常少,所以可以将以这些节点为起点的路径组成的字符串全部加入到一个广义后缀自动机里,然后就可以直接统计 …

题目传送门 这道题是那场比赛里唯一一道比较容易的题目,也是我唯一那道AC的题…… 由于要在si后加字母,而且要保持si为t的子串,这很明显要用到SAM。任何这题就变成了在一张DAG中的某些点上有若干棋子,每次操作要把其中一个棋子沿着DAG的边移动一格,不能操作者负。这就是一个非常裸的博弈论问题了,求 …

一个蒟蒻,在字符串方面只会Hash不会KMP,还有一点点AC自动机,竟然看起了SAM,真的很累。幸好有许多dalao的帮助(包括NBC),还有hihocoder上图文并茂的介绍,当然也有其他论文和博客,我竟然有一点点理(bei)解(xia)了SAM的代码。 对于一个字符串S,它对应的后缀自动机是一个 …

题目传送门 solution: 增量构建后缀自动机,对于一个询问串ch,从S(S为初始状态)开始根据trans函数进行转移,ch是原串的一个子串当且仅当转移没有被丢弃。如果被丢弃了,那么答案显然是零,否则假设最后转移到了状态T,那么答案为|endpos(T)|。那么怎么统计每一个节点的|endpos …