085. Pattern Two

Codeforces

IDCF10269085

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Though you may have completed the previous task to analyze and find patterns in sections of text, the FBI has realized that it needs a more powerful program that is able to find more complex patterns and with more constraints. Your new program should be able to identify if a repetition pattern exists within a string regardless of where it starts. You will also be supplied with a number that represents how many repeats there should be. Your program should only output "True" if the number of repetitions precisely matches the number provided. The first line contains the string to be analyzed. The second line contains a single integer that represents the number of repetitions to look for. A single statement of "True" or "False" that indicates whether or not a repetition pattern exists with the repeat number provided. There can be unneeded text before and after the repetition, and this should be ignored. ## Input The first line contains the string to be analyzed. The second line contains a single integer that represents the number of repetitions to look for. ## Output A single statement of "True" or "False" that indicates whether or not a repetition pattern exists with the repeat number provided. [samples] ## Note There can be unneeded text before and after the repetition, and this should be ignored.

**Definitions** Let $ s \in \Sigma^* $ be the input string over alphabet $ \Sigma $. Let $ r \in \mathbb{Z}^+ $ be the target number of repetitions. **Constraints** 1. $ s $ may contain arbitrary prefix and suffix text. 2. The repetition pattern must be contiguous and non-empty. **Objective** Determine if there exists a non-empty substring $ p \in \Sigma^+ $ and integers $ i, j $ with $ 0 \leq i \leq j \leq |s| $, such that: - $ s[i:j] = p^r $ (i.e., $ p $ repeated exactly $ r $ times), - $ p $ is not a repetition of a smaller substring (i.e., $ p $ is primitive), - and no larger contiguous substring containing $ p^r $ is also a repetition of $ p $ more than $ r $ times. Output "True" if such $ p $ exists with exactly $ r $ repetitions; otherwise, output "False".

API Response (JSON)

{
  "problem": {
    "name": "085. Pattern Two",
    "description": {
      "content": "Though you may have completed the previous task to analyze and find patterns in sections of text, the FBI has realized that it needs a more powerful program that is able to find more complex patterns ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269085"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Though you may have completed the previous task to analyze and find patterns in sections of text, the FBI has realized that it needs a more powerful program that is able to find more complex patterns ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\Sigma^* $ be the input string over alphabet $ \\Sigma $.  \nLet $ r \\in \\mathbb{Z}^+ $ be the target number of repetitions.  \n\n**Constraints**  \n1. $ s $ may contain arbit...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments