D. Autocompletion

Codeforces

IDCF928D

Time1000ms

Memory256MB

Difficulty—

stringstrees

English · Original

Chinese · Translation

Formal · Original

Arcady is a copywriter. His today's task is to type up an already well-designed story using his favorite text editor. Arcady types words, punctuation signs and spaces one after another. Each letter and each sign (including line feed) requires one keyboard click in order to be printed. Moreover, when Arcady has a non-empty prefix of some word on the screen, the editor proposes a possible autocompletion for this word, more precisely one of the already printed words such that its prefix matches the currently printed prefix if this word is unique. For example, if Arcady has already printed «_codeforces_», «_coding_» and «_codeforces_» once again, then there will be no autocompletion attempt for «_cod_», but if he proceeds with «_code_», the editor will propose «_codeforces_». With a single click Arcady can follow the editor's proposal, i.e. to transform the current prefix to it. Note that no additional symbols are printed after the autocompletion (no spaces, line feeds, etc). What is the minimum number of keyboard clicks Arcady has to perform to print the entire text, if he is not allowed to move the cursor or erase the already printed symbols? A word here is a contiguous sequence of latin letters bordered by spaces, punctuation signs and line/text beginnings/ends. Arcady uses only lowercase letters. For example, there are 20 words in «_it's well-known that tic-tac-toe is a paper-and-pencil game for two players, x and o._». ## Input The only line contains Arcady's text, consisting only of lowercase latin letters, spaces, line feeds and the following punctuation signs: «_._», «_,_», «_?_», «_!_», «_'_» and «_\-_». The total amount of symbols doesn't exceed 3·105. It's guaranteed that all lines are non-empty. ## Output Print a single integer — the minimum number of clicks. [samples] ## Note In sample case one it's optimal to use autocompletion for the first instance of «_snowboarding_» after typing up «_sn_» and for the second instance of «_snowboarding_» after typing up «_snowb_». This will save 7 clicks. In sample case two it doesn't matter whether to use autocompletion or not.

Arcady 是一名文案编辑。他今天的任务是使用他最喜欢的文本编辑器输入一篇已经设计好的故事。 Arcady 一个接一个地输入单词、标点符号和空格。每个字母和每个符号（包括换行符）都需要一次键盘点击才能打印出来。此外，当 Arcady 在屏幕上有一个非空的单词前缀时，编辑器会提出一个可能的自动补全建议，即从已经打印过的单词中选择一个，使得其前缀与当前输入的前缀匹配，且该单词是唯一的。例如，如果 Arcady 已经打印过 «_codeforces_»、«_coding_» 和再次打印了 «_codeforces_»，那么对于前缀 «_cod_» 将不会出现自动补全提示；但如果他继续输入 «_code_»，编辑器将提出 «_codeforces_» 作为补全建议。通过一次点击，Arcady 可以接受编辑器的建议，即将当前前缀替换为建议的完整单词。请注意，自动补全后不会额外打印任何符号（如空格、换行符等）。如果 Arcady 不允许移动光标或删除已打印的字符，那么他打印完整个文本所需的最少键盘点击次数是多少？这里的“单词”是指由空格、标点符号以及文本或行的起始/结束边界所包围的连续拉丁字母序列。Arcady 仅使用小写字母。例如，在 «_it's well-known that tic-tac-toe is a paper-and-pencil game for two players, x and o._» 中共有 20 个单词。输入仅有一行，包含 Arcady 的文本，仅由小写拉丁字母、空格、换行符以及以下标点符号组成：«_._»、«_,_»、«_?_»、«_!_»、«_'_» 和 «_-_»。符号总数不超过 #cf_span[3·105]。保证所有行均非空。请输出一个整数——最少的点击次数。在第一个样例中，最优策略是在输入 «_sn_» 后对第一个 «_snowboarding_» 使用自动补全，在输入 «_snowb_» 后对第二个 «_snowboarding_» 使用自动补全。这样可以节省 7 次点击。在第二个样例中，是否使用自动补全无关紧要。 ## Input 输入仅有一行，包含 Arcady 的文本，仅由小写拉丁字母、空格、换行符以及以下标点符号组成：«_._»、«_,_»、«_?_»、«_!_»、«_'_» 和 «_-_»。符号总数不超过 #cf_span[3·105]。保证所有行均非空。 ## Output 请输出一个整数——最少的点击次数。 [samples] ## Note 在第一个样例中，最优策略是在输入 «_sn_» 后对第一个 «_snowboarding_» 使用自动补全，在输入 «_snowb_» 后对第二个 «_snowboarding_» 使用自动补全。这样可以节省 7 次点击。在第二个样例中，是否使用自动补全无关紧要。

**Definitions** Let $ T $ be the input text string over the alphabet $ \Sigma = \{ \text{lowercase letters}, \text{space}, \text{line feed}, ., ,, ?, !, ', - \} $. Let $ W = (w_1, w_2, \dots, w_m) $ be the sequence of words in $ T $, where each word $ w_i $ is a maximal contiguous substring of lowercase letters, delimited by non-letter characters. Let $ P_i $ denote the prefix of $ w_i $ typed manually before triggering autocompletion (possibly the entire word). Let $ \text{prev}(w_i) $ denote the set of all previous occurrences of $ w_i $ in $ W $ before position $ i $. **Constraints** - $ |T| \leq 3 \cdot 10^5 $ - Each word $ w_i $ consists only of lowercase Latin letters. - Autocompletion is only available if the current prefix matches a *unique* previous word exactly. **Objective** Minimize the total number of keyboard clicks to produce $ T $, where: - Each character typed manually costs 1 click. - Autocompletion of a prefix $ p $ of $ w_i $ (i.e., replacing $ p $ with a matching previous word $ w_j $, $ j < i $) costs 1 click and completes the entire word $ w_j $, provided $ p $ is a prefix of exactly one previous word. Let $ c_i $ be the minimal number of clicks needed to type word $ w_i $. Then: $$ c_i = \min \left( |w_i|, \min_{\substack{p \text{ is prefix of } w_i \\ p \text{ matches a unique } w_j, j < i}} \left( |p| + 1 \right) \right) $$ The total minimum clicks is: $$ \sum_{i=1}^{m} c_i + \text{number of non-letter characters in } T $$

Samples

Input #1

snow affects sports such as skiing, snowboarding, and snowmachine travel.
snowboarding is a recreational activity and olympic and paralympic sport.

Output #1

Input #2

'co-co-co, codeforces?!'

Output #2

Input #3

thun-thun-thunder, thunder, thunder
thunder, thun-, thunder
thun-thun-thunder, thunder
thunder, feel the thunder
lightning then the thunder
thunder, feel the thunder
lightning then the thunder
thunder, thunder

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. Autocompletion",
    "description": {
      "content": "Arcady is a copywriter. His today's task is to type up an already well-designed story using his favorite text editor. Arcady types words, punctuation signs and spaces one after another. Each letter a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF928D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Arcady is a copywriter. His today's task is to type up an already well-designed story using his favorite text editor.\n\nArcady types words, punctuation signs and spaces one after another. Each letter a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Arcady 是一名文案编辑。他今天的任务是使用他最喜欢的文本编辑器输入一篇已经设计好的故事。\n\nArcady 一个接一个地输入单词、标点符号和空格。每个字母和每个符号（包括换行符）都需要一次键盘点击才能打印出来。此外，当 Arcady 在屏幕上有一个非空的单词前缀时，编辑器会提出一个可能的自动补全建议，即从已经打印过的单词中选择一个，使得其前缀与当前输入的前缀匹配，且该单词是唯一的。例如，如果 ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T $ be the input text string over the alphabet $ \\Sigma = \\{ \\text{lowercase letters}, \\text{space}, \\text{line feed}, ., ,, ?, !, ', - \\} $.  \nLet $ W = (w_1, w_2, \\dots, w_m)...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments