LibreOJ

2525 「HAOI2018」字串覆盖

内存限制：512 MB 时间限制：3000 ms

题目描述

小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$是给定的参数．一个位置不能被覆盖多次．覆盖操作可以进行任意多次，你需要输出获得收益的最大值．

注意每次询问都是独立的，即进行一次询问后，覆盖的位置会复原．

输入格式

第一行两个整数 $n, K$ ，表示字符串长度和参数．

接下来一行一个字符串 $A$.

接下来一行一个字符串 $B$ .

接下来一行一个整数 $q$ ，表示询问个数．

接下来 $q$ 行，每行四个整数 $s, t, l, r$ ，表示一次询问．

输出格式

输出 $q$ 行，每行一个整数，表示一个询问的答案．

样例

对于第一组询问 $T$ = abcbababa, $P$ = aba，覆盖加粗部分的子串，收益为$K - 5 = 6$. 对于第二组询问 $T$ = cbababab，$P$ = bab, 收益为$(K - 4) + (K - 8) = 10$.

数据范围与提示

对于所有数据，有 $1 \le n, q \le 10^5$ ，$A, B$ 仅由小写英文字母组成，$1 \le s \le t \le n, 1 \le l \le r \le n, n < K \le 10^9$． 对于 $n = 10^5$ 的测试点，满足 $51 \le r - l \le 2000$ 的询问不超过 $11000$ 个，且 $r - l$ 在该区间内均匀随机．

样例

样例输入 1

10 11
abcbababab
ababcbabab
5
1 9 7 9
3 10 8 10
1 10 1 2
5 7 2 3
1 5 3 6

样例输出 1

6
10
22
5
10