题意

求若干串\(T\)在另一个长串\(S\)中各自作为子串出现的次数,匹配的方式为“循环同构”。

分析

循环同构的问题,考虑倍长字符串即可解决。

现在就需要考虑串\(T\)所有结尾位置为\(i\),长度为\(n\)的串是否在\(S\)中出现了。

处理这个的方式我们可以处理出串\(T\)所有结尾位置为\(i\)与\(S\)的最长公共子串的长度,如果最长公共子串的长度\(\ge n\),那么显然,串\(T\)中结尾位置为\(i\)长度为\(n\)的串在\(S\)中出现了。

处理串\(T\)所有结尾位置为\(i\)与\(S\)的最长公共子串的长度,我们记录两个状态来处理,一个是当前状态\(u\),表示\(T_i\)结尾的最长公共子串在\(S\)的 SAM 的哪个状态里;二是当前匹配长度\(l\),表示\(T_i\)结尾的最长公共子串的长度。

  • 如果状态\(u\)存在新字符\(c\)的转移边,那么\(l=l+1,u=t[u][c]\)。
  • 如果不存在这样的转移边,那么就暴力地往\(fa[u]\)跳,直到找到一个有转移边的状态。
  • 如果到根结点也不存在这样的转移边,则\(u=1,l=0\)。

这样的话,我们就可以得到最长的匹配位置。而我们所需要的是正好长度为\(n\)的出现次数,显然这个出现次数\(\ge\)当前的出现次数,于是,从当前的状态\(u\)暴力往前跳找到符合要求的状态即可。

还需要注意的是,为了防止备长字符串以后,重复的子串被重复计算,已经被计算过的状态要搭上 tag 。

 

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注