题意

给出一个字符串和一些询问,每次询问一个子串 $s_ls_{l+1}\cdots s_r$ 中本质不同的回文子串个数。

分析

一个结论:

  • 一个字符串的所有回文后缀的长度,按照长度排序后可以依次划分为 \(k\) 个长度的长差数列,而且 \(k\le log_2n\) 。

考虑暴力的做法:

离线询问对 \(r\) 排序,考虑增加一个字符,右边界到了 \(r\)

显然当前会对答案有影响的,一定是在当前节点的 fail 链上的

在回文树上暴力 fail 统计以 \(r\) 为结尾的新增回文串。

注意到每一个回文串影响的左端点是一个区间,如果这个区间包含了询问的左端点,显然答案的贡献 \(+1\) ,这个区间,一定是上一次这个回文串出现以后或者出现的不完整,也就是区间 [上一次出现这个回文串的开始位置+1,这一次出现这个回文串的位置]

这样直接做的话,时间复杂度是 \(O(n^2logn)\) 。

利用的结论,我们可以把一整段一起处理。

每次需要标记的区间就是 [一整段中长度最长的字符串上一次出现的开始位置+1,一整段中长度最短的字符串开始位置]

长度最长的字符串的开始位置,可以用线段树来维护

区间加单点查询,直接树状数组做就可以

 


发表评论

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