← 返回题目列表

Codeforces · 985/F

F. 同构字符串

中文机器翻译题面 查看原题

给定一个长度为 n 的字符串 s,由小写英文字母组成。

对于两个给定的字符串 s 和 t,假设 S 是 s 的不同字符的集合,T 是 t 的不同字符的集合。如果字符串 s 和 t 的长度相等,并且 S 和 T 之间存在一对一映射(双射)f,其中 f(si) = ti,则它们是同构的。正式:

1. 对于任意索引 i,f(si) = ti,
2. 对于任意字符 $$x \in S$$,在 T$$ 中恰好有一个字符 $$y \in T$$ 满足 f(x) = y,
3. 对于 T$$ 中的任意字符 $$y \in S$$ 中,恰好有一个字符 $$x \in S$$ 满足 f(x) = y。

例如,字符串“aababc”和“bbcbcz”是同构的。字符串“aaaww”和“wwwaa”也是同构的。以下字符串对不是同构的:“aab”和“bbb”、“test”和“best”。

您必须处理 m 个以三个整数 x、y、len (1 ≤ x, y ≤ n - len + 1) 为特征的查询。对于每个查询,检查两个子字符串 s[x... x + len - 1] 和 s[y... y + len - 1] 是否同构。

输入

第一行包含两个空格分隔的整数 n 和 m (1 ≤ n ≤ 2·105, 1 ≤ m ≤ 2·105) — 字符串 s 的长度和查询次数。

第二行包含由n个小写英文字母组成的字符串s。

以下 m 行每行包含一个查询: xi, yi 和 leni (1 ≤ xi, yi ≤ n, 1 ≤ leni ≤ n - max(xi, yi) + 1) — 要检查的子字符串对的描述。

输出

对于单独行中的每个查询,如果子字符串 s[xi... xi + leni - 1] 和 s[yi... yi + leni - 1] 同构,则打印“YES”,否则打印“NO”。

示例

输入 #1

7 4
abacaba
1 1 1
1 4 2
2 1 3
2 4 3

输出 #1

YES
YES
NO
YES

注意

示例中的查询如下:

1.子串“a”和“a”同构:f(a) = a;
2. 子串“ab”和“ca”同构:f(a) = c, f(b) = a;
3. 子串“bac”和“aba”不是同构的,因为 f(b) 和 f(c) 必须同时等于 a;
4. 子串“bac”和“cab”同构:f(b) = c,f(a) = a,f(c) = b。