H. Beautiful Substrings

Codeforces

IDCF10197H

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given two strings a and b consisting of lowercase English letters. A beautiful substring is defined as a substring of any length of string b such that the first and last letters of it are the same as the first and last letters of any substring of length k of string a. Your task is to count the number of beautiful substrings. Can you? The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases. The first line of each test case contains three integers n, m, and k (1 ≤ n, m ≤ 105, 1 ≤ k ≤ n), in which n is the length of string a, m is the length of string b, and k is the described variable in the statement. Then two lines follow, the first line contains a string a of length n and the second line contains a string b of length m. Both strings consist only of lowercase English letters. For each test case, print a single line containing the number of beautiful substrings A substring of a string s is a sequence sl, sl + 1, ..., sr for some integers (l, r) such that (1 ≤ l ≤ r ≤ n), in which n is the length of the string s. ## Input The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.The first line of each test case contains three integers n, m, and k (1 ≤ n, m ≤ 105, 1 ≤ k ≤ n), in which n is the length of string a, m is the length of string b, and k is the described variable in the statement. Then two lines follow, the first line contains a string a of length n and the second line contains a string b of length m. Both strings consist only of lowercase English letters. ## Output For each test case, print a single line containing the number of beautiful substrings [samples] ## Note A substring of a string s is a sequence sl, sl + 1, ..., sr for some integers (l, r) such that (1 ≤ l ≤ r ≤ n), in which n is the length of the string s.

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case: - Let $ n, m, k \in \mathbb{Z} $ denote the lengths of strings $ a $, $ b $, and the fixed substring length, respectively. - Let $ a \in \Sigma^n $, $ b \in \Sigma^m $ be strings over $ \Sigma = \{ \text{a}, \text{b}, \dots, \text{z} \} $. Let $ S_a = \{ (a_i, a_{i+k-1}) \mid i \in \{1, \dots, n-k+1\} \} $ be the set of first-last letter pairs of all length-$ k $ substrings of $ a $. Let $ S_b = \{ (b_j, b_l) \mid 1 \leq j \leq l \leq m \} $ be the set of first-last letter pairs of all substrings of $ b $. **Constraints** 1. $ 1 \leq T \leq 100 $ 2. $ 1 \leq n, m \leq 10^5 $ 3. $ 1 \leq k \leq n $ **Objective** For each test case, compute: $$ \left| S_a \cap S_b \right| $$ where $ S_a \cap S_b $ is the intersection of the two sets of first-last letter pairs.

API Response (JSON)

{
  "problem": {
    "name": "H. Beautiful Substrings",
    "description": {
      "content": "You are given two strings a and b consisting of lowercase English letters. A beautiful substring is defined as a substring of any length of string b such that the first and last letters of it are the ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10197H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two strings a and b consisting of lowercase English letters. A beautiful substring is defined as a substring of any length of string b such that the first and last letters of it are the ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n, m, k \\in \\mathbb{Z} $ denote the lengths of strings $ a $, $ b $, and the fixed substring len...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments