[后缀数组][模板] 求正好出现k次子串个数 HDU6194 string string string

Huh,比赛的时候花了三个小时把这个正解是用后缀自动机的题肝了出来,我也不知道我怎么做到的。

想了很多策略之后发现自己是错的就很难受,最后终于想到正确策略:在height数组上做一个长度为k的滑窗,每次检查滑窗两端点之外的height是否比这一整段内的最小值大,注意这里面的一整段最小值M就是这一整段的公共最长公共前缀的长度,这个东西和他的前缀是在这里出现了k次的,那么怎么知道他是不是在滑窗外面出现呢,和两端点的height比较一下就行了,取两端点中的最大值P,这个说明是之外的点与滑窗两个端点的最大公共前缀,而所有的在滑窗内的满足P<len<=M的前缀都是仅出现了一次的子串!!!

wa的话,需要特判k为1的情况,,因为height这个数组是个间隔定义的东西,所以这种只有一个的需要单独处理,这时候实际上区间内的最长公共前缀就是排名在此的后缀本身

继续阅读“[后缀数组][模板] 求正好出现k次子串个数 HDU6194 string string string”