E. Ali goes shopping

Codeforces

IDCF72E

Time5000ms

Memory256MB

Difficulty—

brute forcestrings

English · Original

Chinese · Translation

Formal · Original

Ali Koochooloo is going to buy new clothes since we're reaching Noruz, the ancient Persian festival and the beginning of new Persian year. When Ali entered a shop, he saw that the shopkeeper was a programmer and since there is no money in programming he had changed his career. The shopkeeper told Ali that he can buy anything for free if he could answer a simple question in 10 seconds. But to see the question Ali has to pay 3 tomans. Ali agreed instantly and the shopkeeper handed him a piece of paper containing the task. The task was indeed very simple. It said: Let string _A_ be _ababababababab_. Which non-empty substring of _A_ is repeated the most times in it? Ali answered fast. He said the answer is _a_. But the shopkeeper said that Ali is wrong and asked him to read the rest of statement: If several substrings have the maximal repeat time, then the substring with maximal length would be the answer, in case of a tie the alphabetically latest substring will be chosen. So the answer is _ab_. Now Ali wants us to solve this problem for different strings. We don't have a great advantage over Ali, we just have a computer and a weird language. ## Input The single line consisting of a string _A_. It is non-empty, made of lower-case Latin letters and contains at most 30 characters. ## Output The single line contains the answer. [samples]

Ali Koochooloo 正准备购买新衣服，因为新年波斯节日诺鲁兹即将来临，这标志着波斯新年的开始。当 Ali 进入一家商店时，他发现店主是一名程序员，但由于编程赚不到钱，他转行做了店主。店主告诉 Ali，如果他能在 #cf_span[10] 秒内回答一个简单的问题，就可以免费购买任何东西。但要看到这个问题，Ali 需要支付 3 托曼。 Ali 立刻同意了，店主递给他一张写有任务的纸。这个任务确实非常简单，上面写着： #cf_span(class=[tex-font-style-underline], body=[设字符串 #cf_span[A] 为 _ababababababab_。在 #cf_span[A] 中，哪个非空子串出现的次数最多？]) Ali 快速回答：答案是 _a_。但店主说 Ali 错了，并让他继续阅读题目的其余部分： #cf_span(class=[tex-font-style-underline], body=[如果多个子串具有最大的重复次数，则选择长度最大的子串作为答案；若长度仍相同，则选择字典序最大的子串。]) 因此，正确答案是 _ab_。现在 Ali 想让我们为不同的字符串解决这个问题。我们并没有比 Ali 更大的优势，只是我们有一台电脑和一种奇怪的语言。输入为一行，包含一个字符串 #cf_span[A]。该字符串非空，由小写拉丁字母组成，长度不超过 #cf_span[30] 个字符。输出为一行，包含答案。 ## Input 输入为一行，包含一个字符串 #cf_span[A]。该字符串非空，由小写拉丁字母组成，长度不超过 #cf_span[30] 个字符。 ## Output 输出为一行，包含答案。 [samples]

**Definitions** Let $ A $ be a non-empty string of length at most 30, consisting of lowercase Latin letters. Let $ \mathcal{S} $ be the set of all non-empty substrings of $ A $. For a substring $ s \in \mathcal{S} $, define $ r(s) $ as the number of (possibly overlapping) occurrences of $ s $ in $ A $. **Constraints** - $ 1 \leq |A| \leq 30 $ - $ A \in \{a, b, \dots, z\}^* $ **Objective** Find the substring $ s^* \in \mathcal{S} $ such that: 1. $ r(s^*) = \max_{s \in \mathcal{S}} r(s) $ (maximal repetition count), 2. If multiple substrings achieve the maximum repetition count, choose the one with maximal length, 3. If there is still a tie, choose the alphabetically latest substring. Output $ s^* $.

Samples

Input #1

abab

Output #1

ab

Input #2

abcd

Output #2

abcd

API Response (JSON)

{
  "problem": {
    "name": "E. Ali goes shopping",
    "description": {
      "content": "Ali Koochooloo is going to buy new clothes since we're reaching Noruz, the ancient Persian festival and the beginning of new Persian year. When Ali entered a shop, he saw that the shopkeeper was a pr",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF72E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ali Koochooloo is going to buy new clothes since we're reaching Noruz, the ancient Persian festival and the beginning of new Persian year.\n\nWhen Ali entered a shop, he saw that the shopkeeper was a pr...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Ali Koochooloo 正准备购买新衣服，因为新年波斯节日诺鲁兹即将来临，这标志着波斯新年的开始。\n\n当 Ali 进入一家商店时，他发现店主是一名程序员，但由于编程赚不到钱，他转行做了店主。店主告诉 Ali，如果他能在 #cf_span[10] 秒内回答一个简单的问题，就可以免费购买任何东西。但要看到这个问题，Ali 需要支付 3 托曼。\n\nAli 立刻同意了，店主递给他一张写有任务的纸。这...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ A $ be a non-empty string of length at most 30, consisting of lowercase Latin letters.  \nLet $ \\mathcal{S} $ be the set of all non-empty substrings of $ A $.  \n\nFor a substring...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments