{"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 same as the first and last letters of any substring of length k of string a.\n\nYour task is to count the number of beautiful substrings. Can you?\n\nThe first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.\n\nThe 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. \n\nThen 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.\n\nFor each test case, print a single line containing the number of beautiful substrings\n\nA 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.\n\n## Input\n\nThe 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.\n\n## Output\n\nFor each test case, print a single line containing the number of beautiful substrings\n\n[samples]\n\n## Note\n\nA 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.","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 length, respectively.  \n- Let $ a \\in \\Sigma^n $, $ b \\in \\Sigma^m $ be strings over $ \\Sigma = \\{ \\text{a}, \\text{b}, \\dots, \\text{z} \\} $.  \n\nLet $ 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 $.  \nLet $ 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 $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 100 $  \n2. $ 1 \\leq n, m \\leq 10^5 $  \n3. $ 1 \\leq k \\leq n $  \n\n**Objective**  \nFor each test case, compute:  \n$$\n\\left| S_a \\cap S_b \\right|\n$$  \nwhere $ S_a \\cap S_b $ is the intersection of the two sets of first-last letter pairs.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10197H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}