七分遮等八分治啥封和遮的意思是什么

来源：蜘蛛抓取(WebSpider) 时间：2020-06-19 00:04 标签： 遮是什么意思

q次询问每次给定长度为 [a,b]，求对於所有

0

看上去很不可做但是有一个很难注意到的特殊性质：所有 0

k,q中的较小值是根号级别的，考虑数据分治

k<q时字符串很短，直接开 k2个vector记錄所有区间出现的位置然后暴力枚举 w的子串，在对应的vector用 b二分一下算出有多少个区间乘上在后缀自动机上的size。复杂度

k>q时询问很少，鈳以每次单独处理每次读入 S的子串 的 后缀长度

[a,b]中的区间挂到 r上，从左到右扫一遍设当前处理 Lr?<r?l+1，说明这个子串没有出现过直接跳過；否则在fail树上倍增找到最靠上的满足

我要回帖

更多关于 遮是什么意思 的文章

 

随机推荐