F. String Compression

Codeforces

IDCF825F

Time2000ms

Memory512MB

Difficulty—

dphashingstring suffix structuresstrings

English · Original

Chinese · Translation

Formal · Original

Ivan wants to write a letter to his friend. The letter is a string _s_ consisting of lowercase Latin letters. Unfortunately, when Ivan started writing the letter, he realised that it is very long and writing the whole letter may take extremely long time. So he wants to write the _compressed version_ of string _s_ instead of the string itself. The _compressed version_ of string _s_ is a sequence of strings _c_1, _s_1, _c_2, _s_2, ..., _c__k_, _s__k_, where _c__i_ is the decimal representation of number _a__i_ (without any leading zeroes) and _s__i_ is some string consisting of lowercase Latin letters. If Ivan writes string _s_1 exactly _a_1 times, then string _s_2 exactly _a_2 times, and so on, the result will be string _s_. The length of a _compressed version_ is |_c_1| + |_s_1| + |_c_2| + |_s_2|... |_c__k_| + |_s__k_|. Among all _compressed versions_ Ivan wants to choose a version such that its length is minimum possible. Help Ivan to determine minimum possible length. ## Input The only line of input contains one string _s_ consisting of lowercase Latin letters (1 ≤ |_s_| ≤ 8000). ## Output Output one integer number — the minimum possible length of a _compressed version_ of _s_. [samples] ## Note In the first example Ivan will choose this compressed version: _c_1 is _10_, _s_1 is _a_. In the second example Ivan will choose this compressed version: _c_1 is _1_, _s_1 is _abcab_. In the third example Ivan will choose this compressed version: _c_1 is _2_, _s_1 is _c_, _c_2 is _1_, _s_2 is _z_, _c_3 is _4_, _s_3 is _ab_.

Ivan 想给他的朋友写一封信。这封信是一个由小写拉丁字母组成的字符串 #cf_span[s]。不幸的是，当 Ivan 开始写信时，他意识到信太长了，写完整封信可能需要极长的时间。因此，他希望写字符串 #cf_span[s] 的 _压缩版本_，而不是直接写原字符串。字符串 #cf_span[s] 的 _压缩版本_ 是一个字符串序列 #cf_span[c1, s1, c2, s2, ..., ck, sk]，其中 #cf_span[ci] 是数字 #cf_span[ai] 的十进制表示（不含前导零），而 #cf_span[si] 是由小写拉丁字母组成的某个字符串。如果 Ivan 将字符串 #cf_span[s1] 重复写恰好 #cf_span[a1] 次，然后将 #cf_span[s2] 重复写恰好 #cf_span[a2] 次，依此类推，最终得到的字符串就是 #cf_span[s]。一个 _压缩版本_ 的长度定义为 #cf_span[|c1| + |s1| + |c2| + |s2| + ... + |ck| + |sk|]。在所有可能的 _压缩版本_ 中，Ivan 希望选择一个长度最小的版本。请帮助 Ivan 确定最小可能的长度。输入仅包含一行，一个由小写拉丁字母组成的字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 8000]）。请输出一个整数——#cf_span[s] 的 _压缩版本_ 的最小可能长度。在第一个示例中，Ivan 将选择以下压缩版本：#cf_span[c1] 为 _10_，#cf_span[s1] 为 _a_。在第二个示例中，Ivan 将选择以下压缩版本：#cf_span[c1] 为 _1_，#cf_span[s1] 为 _abcab_。在第三个示例中，Ivan 将选择以下压缩版本：#cf_span[c1] 为 _2_，#cf_span[s1] 为 _c_，#cf_span[c2] 为 _1_，#cf_span[s2] 为 _z_，#cf_span[c3] 为 _4_，#cf_span[s3] 为 _ab_。 ## Input 输入仅包含一行，一个由小写拉丁字母组成的字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 8000]）。 ## Output 请输出一个整数——#cf_span[s] 的 _压缩版本_ 的最小可能长度。 [samples] ## Note 在第一个示例中，Ivan 将选择以下压缩版本：#cf_span[c1] 为 _10_，#cf_span[s1] 为 _a_。在第二个示例中，Ivan 将选择以下压缩版本：#cf_span[c1] 为 _1_，#cf_span[s1] 为 _abcab_。在第三个示例中，Ivan 将选择以下压缩版本：#cf_span[c1] 为 _2_，#cf_span[s1] 为 _c_，#cf_span[c2] 为 _1_，#cf_span[s2] 为 _z_，#cf_span[c3] 为 _4_，#cf_span[s3] 为 _ab_。

**Definitions** Let $ s \in \Sigma^* $ be the input string, where $ \Sigma = \{a, b, \dots, z\} $ and $ 1 \leq |s| \leq 8000 $. A *compressed version* of $ s $ is a sequence of pairs $ (c_1, s_1), (c_2, s_2), \dots, (c_k, s_k) $, where: - Each $ s_i \in \Sigma^+ $ is a non-empty string of lowercase letters. - Each $ c_i \in \mathbb{Z}^+ $ is a positive integer (represented in decimal without leading zeros). - The concatenation $ \underbrace{s_1 s_1 \cdots s_1}_{c_1 \text{ times}} \underbrace{s_2 s_2 \cdots s_2}_{c_2 \text{ times}} \cdots \underbrace{s_k s_k \cdots s_k}_{c_k \text{ times}} = s $. The *length* of the compressed version is $ \sum_{i=1}^k (|c_i| + |s_i|) $, where $ |c_i| $ denotes the number of decimal digits in $ c_i $. **Objective** Minimize $ \sum_{i=1}^k (|c_i| + |s_i|) $ over all valid compressed versions of $ s $. **Constraints** - $ 1 \leq |s| \leq 8000 $ - Each $ s_i $ must be a contiguous substring of $ s $, and the decomposition must exactly reconstruct $ s $. - Each $ c_i \geq 1 $, and $ c_i \cdot |s_i| \leq |s| $. - The decomposition must be a partition of $ s $ into repeated blocks: $ s = (s_1)^{c_1} (s_2)^{c_2} \cdots (s_k)^{c_k} $.

Samples

Input #1

aaaaaaaaaa

Output #1

Input #2

abcab

Output #2

Input #3

cczabababab

Output #3

API Response (JSON)

{
  "problem": {
    "name": "F. String Compression",
    "description": {
      "content": "Ivan wants to write a letter to his friend. The letter is a string _s_ consisting of lowercase Latin letters. Unfortunately, when Ivan started writing the letter, he realised that it is very long and",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF825F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ivan wants to write a letter to his friend. The letter is a string _s_ consisting of lowercase Latin letters.\n\nUnfortunately, when Ivan started writing the letter, he realised that it is very long and...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Ivan 想给他的朋友写一封信。这封信是一个由小写拉丁字母组成的字符串 #cf_span[s]。\n\n不幸的是，当 Ivan 开始写信时，他意识到信太长了，写完整封信可能需要极长的时间。因此，他希望写字符串 #cf_span[s] 的 _压缩版本_，而不是直接写原字符串。\n\n字符串 #cf_span[s] 的 _压缩版本_ 是一个字符串序列 #cf_span[c1, s1, c2, s2, ...,...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\Sigma^* $ be the input string, where $ \\Sigma = \\{a, b, \\dots, z\\} $ and $ 1 \\leq |s| \\leq 8000 $.  \nA *compressed version* of $ s $ is a sequence of pairs $ (c_1, s_1),...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments