H. The Universal String

Codeforces

IDCF10215H

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Have you ever heard about the universal string? This is the largest string in the world, and it is the mother of all strings that will ever exist in any programming language! The universal string is an infinite string built by repeating the string "_abcdefghijklmnopqrstuvwxyz_" infinitely. So, the universal string will look like this: You are given a string $p$ and your task is to determine if $p$ is a substring of the universal string. Can you? A _substring_ of $s$ is a non-empty string $x$ = $s$[$l$$\\dots$ $r$] = $s_l$$s_{l + 1}$$\\dots$ $s_r$ (1 $<=$ $l$ $<=$ $r$ $<=$ |$s$|). For example, "_code_" and "_force_" are substring of "_codeforces_", while "_coders_" is not. The first line contains an integer $T$ ($1 <= T <= 10^3$) specifying the number of test cases. Each test consists of a single line containing a non-empty string $p$ of length no more $10^3$ and consisting only of lowercase English letters. For each test case, print "_YES_" (without quotes) if the given string is a substring of the universal string. Otherwise, print "_NO_" (without quotes). ## Input The first line contains an integer $T$ ($1 <= T <= 10^3$) specifying the number of test cases.Each test consists of a single line containing a non-empty string $p$ of length no more $10^3$ and consisting only of lowercase English letters. ## Output For each test case, print "_YES_" (without quotes) if the given string is a substring of the universal string. Otherwise, print "_NO_" (without quotes). [samples]

**Definitions** Let $ U = (\texttt{abcdefghijklmnopqrstuvwxyz})^\infty $ be the infinite periodic string formed by repeating the alphabet $ \texttt{"abcdefghijklmnopqrstuvwxyz"} $ indefinitely. Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $, let $ p_k $ be a non-empty string of length at most $ 10^3 $, consisting only of lowercase English letters. **Constraints** 1. $ 1 \le T \le 10^3 $ 2. For each $ k $, $ 1 \le |p_k| \le 10^3 $ and $ p_k \in \{\texttt{a}, \dots, \texttt{z}\}^* $ **Objective** For each $ k \in \{1, \dots, T\} $, determine whether $ p_k $ is a substring of $ U $, i.e., whether there exists an integer $ i \ge 0 $ such that: $$ U[i:i+|p_k|] = p_k $$ Output "YES" if true, "NO" otherwise.

API Response (JSON)

{
  "problem": {
    "name": "H. The Universal String",
    "description": {
      "content": "Have you ever heard about the universal string? This is the largest string in the world, and it is the mother of all strings that will ever exist in any programming language! The universal string is ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10215H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Have you ever heard about the universal string? This is the largest string in the world, and it is the mother of all strings that will ever exist in any programming language!\n\nThe universal string is ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ U = (\\texttt{abcdefghijklmnopqrstuvwxyz})^\\infty $ be the infinite periodic string formed by repeating the alphabet $ \\texttt{\"abcdefghijklmnopqrstuvwxyz\"} $ indefinitely.  \n\nL...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments