P4493 [HAOI2018] 字串覆盖

小C对字符串颇有研究，他觉得传统的字符串匹配太无聊了，于是他想到了这 样一个问题． 对于两个长度为n的串A, B, 小C每次会给出给出4个参数s, t, l, r. 令A从s到t的 子串(从1开始标号)为T，令B从l到r的子串为P.然后他会进行下面的操作： 如果T的某个子串与P相同，我们就可以删掉T的这个子串，并获得K − i的收 益，其中i是初始时A中(注意不是T中)这个子串的起始位置，K是给定的参数． 删除操作可以进行任意多次，你需要输出获得收益的最大值． 注意每次询问都是独立的，即进行一次询问后，删掉的位置会复原．

无

无

样例1解释  子任务 对于所有数据，有 $ 1 ≤ n, q ≤ 10^5 $ ，A, B仅由小写英文字母组成，$ 1 ≤ s ≤ t ≤n $ , $ 1 ≤ l ≤ r ≤ n $ , $ n < K ≤ 10^9 $ ． HAOI2018 round1 T3 对于 $ n = 10^5 $ 的测试点，满足51≤r−l≤2*10^3 的询问不超过11000个，且r−l在该区间内均匀随机 数据范围