[CERC2019] ABB

Luogu
IDLGP9606
Time1000ms
Memory128MB
DifficultyP4
字符串2019哈希 hashingKMP 算法Manacher 算法ICPCCERC
Fernando 受雇于滑铁卢大学,负责完成该大学不久前开始的一个开发项目。在校园外,该大学希望为重要的外国游客和合作者建造具有代表性的平房街。 目前,这条街只建了一部分,它从湖岸开始,一直延伸到森林尽头。Fernando 的任务是通过在森林尽头建造更多的平房来完成这条街。所有现有的平房都坐落在街道的一侧,新的平房应该建在同一侧。这些平房有各种各样的类型,漆成各种各样的颜色。 在 Fernando 看来,整条街的布局有点混乱。他担心增加新平房后,它会看起来更加混乱。所以他想通过为新平房选择合适的颜色来增加一些排列顺序。当项目完成时,平房的整个颜色序列将是对称的,也就是说,从街道的两端观察时,颜色序列是相同的。 在其他问题中,Fernando 想知道,在满足平房颜色限制的情况下,他最少需要用来建造和适当染色才能完成项目的新平房数量。 ### 简要题意 求使给定小写字母字符串成为回文串需在字符串末尾加入字母的最少数量。 ## Input 第一行包含一个整数 $N\ (1\le N\le 4\times 10^5)$,代表街道上现有平房的数量。 第二行包含一个由 $N$ 个小写字母(从 `a` 到 `z`)组成的字符串,代表从湖岸开始的街道现有的平房颜色顺序,其中不同的字母表示不同的颜色。 ## Output 输出一个整数,代表满足 Fernando 要求的新平房的最少数量。 [samples] ## Background **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[ABB](https://contest.felk.cvut.cz/19cerc/solved/abb.pdf)」**
Samples
Input #1
3
abb
Output #1
1
Input #2
12
recakjenecep
Output #2
11
Input #3
15
murderforajarof
Output #3
6
API Response (JSON)
{
  "problem": {
    "name": "[CERC2019] ABB",
    "description": {
      "content": "Fernando 受雇于滑铁卢大学,负责完成该大学不久前开始的一个开发项目。在校园外,该大学希望为重要的外国游客和合作者建造具有代表性的平房街。 目前,这条街只建了一部分,它从湖岸开始,一直延伸到森林尽头。Fernando 的任务是通过在森林尽头建造更多的平房来完成这条街。所有现有的平房都坐落在街道的一侧,新的平房应该建在同一侧。这些平房有各种各样的类型,漆成各种各样的颜色。 在 Fernan",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9606"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Fernando 受雇于滑铁卢大学,负责完成该大学不久前开始的一个开发项目。在校园外,该大学希望为重要的外国游客和合作者建造具有代表性的平房街。\n\n目前,这条街只建了一部分,它从湖岸开始,一直延伸到森林尽头。Fernando 的任务是通过在森林尽头建造更多的平房来完成这条街。所有现有的平房都坐落在街道的一侧,新的平房应该建在同一侧。这些平房有各种各样的类型,漆成各种各样的颜色。\n\n在 Fernan...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments