7091：重叠的子串

题目描述

给定一个只含小写字母的字符串 $s$ 和 $q$ 次询问，每次询问给定一个字符串，以 $s[l .. r]$ 的形式给出，判断 $s$ 中是否存在两个或多个出现的有重叠部分的给定子串。比如在 “ababa” 中，两个 “aba” 子串就重叠于中间的字母 “a”，而两个 “ab” 子串就没有发生重叠。$T$ 组数据。

输入解释

第一行一个正整数 $T(1\le T \le 20)$，表示数据组数。

对于每组数据：

第一行两个整数 $n,q\,(1\le n \le 10^5, 1\le q \le 10^6)$，表示给定字符串的长度及询问个数。

第二行一个长度为 $n$，且只包含小写字母的字符串 $s$。

接下来 $q$ 行，每行两个整数 $l,r\,(1\le l \le r \le n)$，表示一次询问。

保证所有数据的 $\sum n \le 6\times 10^5, \sum q \le 3\times 10^6$。

输出解释

对于每组数据：

输出共 $q$ 行，每行一个字符串 “Yes” 或者 “No”（均不含引号），分别表示存在以及不存在有重叠部分的多个子串 $s[l .. r]$。

输入样例

2
10 3
georgeorge
1 5
1 4
5 10
18 5
huaweihuaweihuawei
1 2
3 6
7 11
12 18
1 18

输出样例

Yes
No
Yes
No
No
No
Yes
No

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2021CCPC华为云挑战赛

源链接： HDU-7091

最后修改于 2021-10-23T19:11:24+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
20000/10000MS(Java/Others)	524288/524288K(Java/Others)