082. Patterns 1

Codeforces

IDCF10269082

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

The FBI has been working hard to find the location of a criminal organization by analyzing their use of repeating patterns in sections of their internal communications. So far, this process has been entirely manual and is therefore slow, so you are tasked with creating a program to automate this pattern finding. Determine whether or not a section of text repeats a single string multiple times. The problem is that you don't know what string it is that is being repeated, though you do know that the pattern will always begin immediately. A pattern will always appear as the same string being repeated at least twice. It is also important to note that there can be unimportant text that follows the repetition that is not a part of the pattern. All of this following text should be ignored. It is also important to note that the repeated string must be at least two characters. A single string that represents the string to analyze. A single statement of "True" or "False" that states whether or not there is a pattern. ## Input A single string that represents the string to analyze. ## Output A single statement of "True" or "False" that states whether or not there is a pattern. [samples]

**Definitions** Let $ s \in \Sigma^* $ be the input string of length $ n = |s| $, where $ \Sigma $ is a finite alphabet. **Constraints** 1. $ n \geq 4 $ (since the repeated substring must be at least 2 characters and appear at least twice). 2. The pattern must start at index 0. 3. Let $ p \in \Sigma^* $ be a substring such that $ |p| \geq 2 $, and $ s $ begins with $ p^k $ for some integer $ k \geq 2 $. 4. The remainder of $ s $ after $ p^k $ (if any) is irrelevant and may be ignored. **Objective** Determine whether there exists an integer $ \ell \in \mathbb{Z} $, $ 2 \leq \ell \leq \lfloor n/2 \rfloor $, such that: $$ s[0:\ell] = s[\ell:2\ell] = \dots = s[(k-1)\ell:k\ell] \quad \text{and} \quad k\ell \leq n, \; k \geq 2 $$ Output "True" if such $ \ell $ exists; otherwise, output "False".

API Response (JSON)

{
  "problem": {
    "name": "082. Patterns 1",
    "description": {
      "content": "The FBI has been working hard to find the location of a criminal organization by analyzing their use of repeating patterns in sections of their internal communications. So far, this process has been e",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269082"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The FBI has been working hard to find the location of a criminal organization by analyzing their use of repeating patterns in sections of their internal communications. So far, this process has been e...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\Sigma^* $ be the input string of length $ n = |s| $, where $ \\Sigma $ is a finite alphabet.  \n\n**Constraints**  \n1. $ n \\geq 4 $ (since the repeated substring must be at...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments