English · Original
Chinese · Translation
Formal · Original
You are given a string _s_ of length _n_ consisting of lowercase English letters.
For two given strings _s_ and _t_, say _S_ is the set of distinct characters of _s_ and _T_ is the set of distinct characters of _t_. The strings _s_ and _t_ are _isomorphic_ if their lengths are equal and there is a one-to-one mapping (bijection) _f_ between _S_ and _T_ for which _f_(_s__i_) = _t__i_. Formally:
1. _f_(_s__i_) = _t__i_ for any index _i_,
2. for any character there is exactly one character that _f_(_x_) = _y_,
3. for any character there is exactly one character that _f_(_x_) = _y_.
For example, the strings "_aababc_" and "_bbcbcz_" are isomorphic. Also the strings "_aaaww_" and "_wwwaa_" are isomorphic. The following pairs of strings are not isomorphic: "_aab_" and "_bbb_", "_test_" and "_best_".
You have to handle _m_ queries characterized by three integers _x_, _y_, _len_ (1 ≤ _x_, _y_ ≤ _n_ - _len_ + 1). For each query check if two substrings _s_\[_x_... _x_ + _len_ - 1\] and _s_\[_y_... _y_ + _len_ - 1\] are isomorphic.
## Input
The first line contains two space-separated integers _n_ and _m_ (1 ≤ _n_ ≤ 2·105, 1 ≤ _m_ ≤ 2·105) — the length of the string _s_ and the number of queries.
The second line contains string _s_ consisting of _n_ lowercase English letters.
The following _m_ lines contain a single query on each line: _x__i_, _y__i_ and _len__i_ (1 ≤ _x__i_, _y__i_ ≤ _n_, 1 ≤ _len__i_ ≤ _n_ - _max_(_x__i_, _y__i_) + 1) — the description of the pair of the substrings to check.
## Output
For each query in a separate line print "_YES_" if substrings _s_\[_x__i_... _x__i_ + _len__i_ - 1\] and _s_\[_y__i_... _y__i_ + _len__i_ - 1\] are isomorphic and "_NO_" otherwise.
[samples]
## Note
The queries in the example are following:
1. substrings "_a_" and "_a_" are isomorphic: _f_(_a_) = _a_;
2. substrings "_ab_" and "_ca_" are isomorphic: _f_(_a_) = _c_, _f_(_b_) = _a_;
3. substrings "_bac_" and "_aba_" are not isomorphic since _f_(_b_) and _f_(_c_) must be equal to _a_ at same time;
4. substrings "_bac_" and "_cab_" are isomorphic: _f_(_b_) = _c_, _f_(_a_) = _a_, _f_(_c_) = _b_.
[{"iden":"statement","content":"你被给定一个长度为 #cf_span[n] 的字符串 #cf_span[s]，由小写英文字母组成。\n\n对于两个给定的字符串 #cf_span[s] 和 #cf_span[t]，设 #cf_span[S] 是 #cf_span[s] 的不同字符的集合，#cf_span[T] 是 #cf_span[t] 的不同字符的集合。如果两个字符串长度相等，并且存在一个从 #cf_span[S] 到 #cf_span[T] 的一一映射（双射）#cf_span[f]，使得 #cf_span[f(si) = ti]，则称这两个字符串是 _同构的_。形式化地：\n\n例如，字符串 \"_aababc_\" 和 \"_bbcbcz_\" 是同构的。字符串 \"_aaaww_\" 和 \"_wwwaa_\" 也是同构的。以下字符串对不是同构的：\"_aab_\" 和 \"_bbb_\"，\"_test_\" 和 \"_best_\"。\n\n你需要处理 #cf_span[m] 个查询，每个查询由三个整数 #cf_span[x, y, len]（#cf_span[1 ≤ x, y ≤ n - len + 1]）描述。对于每个查询，检查两个子串 #cf_span[s[x... x + len - 1]] 和 #cf_span[s[y... y + len - 1]] 是否同构。\n\n第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 2·105], #cf_span[1 ≤ m ≤ 2·105]）——字符串 #cf_span[s] 的长度和查询数量。\n\n第二行包含一个由 #cf_span[n] 个小写英文字母组成的字符串 #cf_span[s]。\n\n接下来的 #cf_span[m] 行，每行包含一个查询：#cf_span[xi], #cf_span[yi] 和 #cf_span[leni]（#cf_span[1 ≤ xi, yi ≤ n], #cf_span[1 ≤ leni ≤ n - max(xi, yi) + 1]）——描述需要检查的两个子串。\n\n对于每个查询，在单独一行中输出 \"_YES_\" 如果子串 #cf_span[s[xi... xi + leni - 1]] 和 #cf_span[s[yi... yi + leni - 1]] 同构，否则输出 \"_NO_\"。\n\n示例中的查询如下：\n\n"},{"iden":"input","content":"第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 2·105], #cf_span[1 ≤ m ≤ 2·105]）——字符串 #cf_span[s] 的长度和查询数量。第二行包含一个由 #cf_span[n] 个小写英文字母组成的字符串 #cf_span[s]。接下来的 #cf_span[m] 行，每行包含一个查询：#cf_span[xi], #cf_span[yi] 和 #cf_span[leni]（#cf_span[1 ≤ xi, yi ≤ n], #cf_span[1 ≤ leni ≤ n - max(xi, yi) + 1]）——描述需要检查的两个子串。"},{"iden":"output","content":"对于每个查询，在单独一行中输出 \"_YES_\" 如果子串 #cf_span[s[xi... xi + leni - 1]] 和 #cf_span[s[yi... yi + leni - 1]] 同构，否则输出 \"_NO_\"。"},{"iden":"note","content":"示例中的查询如下：\n子串 \"_a_\" 和 \"_a_\" 是同构的：#cf_span[f(a) = a]；\n子串 \"_ab_\" 和 \"_ca_\" 是同构的：#cf_span[f(a) = c], #cf_span[f(b) = a]；\n子串 \"_bac_\" 和 \"_aba_\" 不是同构的，因为 #cf_span[f(b)] 和 #cf_span[f(c)] 必须同时等于 #cf_span[a]；\n子串 \"_bac_\" 和 \"_cab_\" 是同构的：#cf_span[f(b) = c], #cf_span[f(a) = a], #cf_span[f(c) = b]。 "}]}
Let $ s $ be a string of length $ n $ over the alphabet $ \Sigma = \{a, b, \dots, z\} $.
For any substring $ s[i..i+\ell-1] $, define its **character pattern** as the sequence of integers $ p_1, p_2, \dots, p_\ell $, where $ p_j $ is the index (starting from 1) of the first occurrence of the character $ s[i+j-1] $ within the substring $ s[i..i+\ell-1] $.
Two substrings $ s[x..x+\ell-1] $ and $ s[y..y+\ell-1] $ are **isomorphic** if and only if their character patterns are identical.
Given $ m $ queries, each specified by $ (x, y, \ell) $, determine whether the character patterns of $ s[x..x+\ell-1] $ and $ s[y..y+\ell-1] $ are equal.
**Input:**
- $ n, m \in \mathbb{N} $, $ 1 \leq n, m \leq 2 \cdot 10^5 $
- String $ s \in \Sigma^n $
- $ m $ triples $ (x_i, y_i, \ell_i) $, $ 1 \leq x_i, y_i \leq n $, $ 1 \leq \ell_i \leq n - \max(x_i, y_i) + 1 $
**Output:**
For each query $ i $, output "YES" if $ \text{pattern}(s[x_i..x_i+\ell_i-1]) = \text{pattern}(s[y_i..y_i+\ell_i-1]) $, otherwise "NO".
---
**Formal Definition of Character Pattern:**
For a substring $ u = s[i..i+\ell-1] $, define $ f_u : \{1, \dots, \ell\} \to \mathbb{N} $ by:
$$
f_u(j) = \min \{ k \in \{1, \dots, j\} \mid u[k] = u[j] \}
$$
Then the **pattern** of $ u $ is the sequence $ (f_u(1), f_u(2), \dots, f_u(\ell)) $.
Two substrings are isomorphic iff their patterns are identical.
API Response (JSON)
{
"problem": {
"name": "F. Isomorphic Strings",
"description": {
"content": "You are given a string _s_ of length _n_ consisting of lowercase English letters. For two given strings _s_ and _t_, say _S_ is the set of distinct characters of _s_ and _T_ is the set of distinct ch",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF985F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given a string _s_ of length _n_ consisting of lowercase English letters.\n\nFor two given strings _s_ and _t_, say _S_ is the set of distinct characters of _s_ and _T_ is the set of distinct ch...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"你被给定一个长度为 #cf_span[n] 的字符串 #cf_span[s]，由小写英文字母组成。\\n\\n对于两个给定的字符串 #cf_span[s] 和 #cf_span[t]，设 #cf_span[S] 是 #cf_span[s] 的不同字符的集合，#cf_span[T] 是 #cf_span[t] 的不同字符的集合。如果两个字符...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ s $ be a string of length $ n $ over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $.\n\nFor any substring $ s[i..i+\\ell-1] $, define its **character pattern** as the sequence of integers $ p_1, p_2,...",
"is_translate": false,
"language": "Formal"
}
]
}