题面 传送门:SPOJ 694 Solution 这题可以用SAM来搞,也可以用SA来搞。但无论是哪种搞法,都是基本操作。下面我们来分别讲解一下怎么搞。 SAM 这题用SAM来求就十分粗暴简单。不会SAM的小伙伴可以戳这里 首先,我们先把SAM建出来。根据SAM的性质,我们从出发点随着SAM任意走,走到哪里都是一个完全不同的子串。因此,我们只需要对SAM做一个拓扑序DP/记忆化搜索即可求出SAM上的路径总数,既不同子串的数量。 SA 这题我们显然还是要把后缀数组和height建出来的,不会SA的小伙伴可以戳这里 我…