Suppose a string s of size n is given. Now you have to answer the minimum number of characters to append at the end to make it a palindrome. How to solve this problem in O(n) time complexity?
Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | adamant | 157 |
| 4 | maroonrk | 154 |
| 5 | -is-this-fft- | 148 |
| 5 | atcoder_official | 148 |
| 5 | SecondThread | 148 |
| 8 | Petr | 147 |
| 9 | TheScrasse | 145 |
| 9 | nor | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.07.2024 01:17:59 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
What is the source of this problem?
https://community.topcoder.com/stat?c=problem_statement&pm=10182. What I asked is kind of modified version of this problem. But the constraint of this problem is too low. So any O(n^2) brute force solution works. But how to solve this in O(n)?
The number of characters you need to append is equal to $$$n$$$ minus the length of the longest palindromic suffix. You can find this in $$$O(n)$$$ with hashing/Manacher's/something.
Why is this true? Imagine the string as a concatenation of $$$AB$$$, where $$$A$$$ is the beginning of the string and $$$B$$$ is the longest palindromic suffix. Let $$$|x|$$$ denote the length of the string $$$x$$$. Obviously this is an upper bound to the answer, as $$$|A|$$$ = $$$n - |B|$$$ and you can just append the reverse of $$$A$$$.
It's also a lower bound. Let's say there was some $$$C$$$ that you could append where $$$|C| < |A|$$$. Then, you can imagine the new string with appended characters like this: $$$ABC$$$, where the whole string is a palindrome. That means the string is also [reverse of $$$C$$$] + $$$DBC$$$ where $$$D$$$ is the part of $$$A$$$ that isn't part of the reverse of $$$C$$$. But this must mean that $$$DB$$$ is also a palindrome. Because $$$DB$$$ is a suffix of the string, this must mean that $$$B$$$ was not the longest palindromic suffix, and thus we have a contradiction.
So the answer is exactly $$$|A|$$$, or for the Topcoder problem, $$$2|A| + |B|$$$.
if you want o(n) you can use KMP algoritm which take O(n) you can use it to get the longest palindrom from end of string for example: this string abcdc would be 2 because the substr 'cdc' is palindrome so we must append 2 chars . you can look to my code (https://codeforces.com/contest/1326/submission/73817581) which i use in it kmp algorithm to find prefix and suffix palindrome
hope it well
We simply need to find the longest suffix palindrome of s.
1)Reverse the string. Let the new string be r.
2)Calculate the prefix function of r.(U can read about the same at cp-algorithms)
3)Take the maximum i such that pi[i]>=floor(i/2).
Answer is (n-i). As 1 ...... i is the longest prefix palindrome of r => n-i+1 ..... n is the longest suffix palindrome for s.