I know that using Manacher's algorithm, we can find all pairs ($$$i$$$, $$$j$$$) such that s[i $$$\dots$$$ j] is a palindrome. This article on cp-algorithms uses 2 vectors, one in which the $$$i$$$ is the center of an odd length palindrome, the other in which the $$$i$$$ is the latter of the 2 middle elements of an even length palindrome. But how do we convert this information into a vector<pair<int, int>> where the pair represents the boundaries of the palindrome substring?
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
21:02:25
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
21:02:25
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 20:32:35 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
Are you sure that is solvable in O(N)?
Which is solvable in $$$O(n)$$$? Manacher's algo or my question?
Your ofc.
IDK
I don't think you can solve in O(N). The best I can tell you is O(N^2) solution, where you fix the ends of the substring and check in O(1) is it palindrome or not. I would use hashing to check since I'm not aware of any other string techniques.
BTW It is very interesting whether O(N) solution exists or not.
How would you use hashing to figure out if a substring is a palindrome? Also, how would you get a substring of a string given the endpoints in $$$O(1)$$$. String.substr method is linear.
I think you don't understand hashing. You pre-calculate stuff and then check in O(1).
But how would you get the substring of a string in $$$O(1)$$$?
You don't need the substring itself to get a hash of that substring, because you have pre-calculated things already. Well, if you have still doubts, check out some hashing tutorial!
If you have a palindromic string, the string will stay palindrome after popping a character from the front and from the back.
You can use this to get that vector you want from the Mancher vectors. Mancher vector has info about the largest subpalindrome centered at $$$i$$$. If that subpalindrome is $$$s[l .. r]$$$ then $$$s[l + k .. r - k]$$$ is also a palindrome for all $$$k$$$, $$$l + k \leq r - k$$$ (Imagine popping $$$k$$$ characters from the front and from the back). You can bruteforce this to get your desired vector but be careful that its size will be $$$O(n^2)$$$.
There are other info that can be calculated in $$$O(n)$$$ that you may probably find useful instead of that $$$n^2$$$ sized borders vector you're looking for.
Here is some code that calculates how many subpalindromes start, finish, or cover index $$$i$$$: https://ideone.com/d77lMo If you're interested in this, I can provide an explanation for what the code is doing.
Is there a way to get the boundaries of all substrings that are palindromes of a string in $$$O(n^{2})$$$ or less?
I've already told you O(n^2) approach.
The less is impossible since you can have as much as (n+1)*n/2 substrings in total (when all the characters are same). How could you construct the vector with let's say n^2 values in less than n^2 time? It's impossible.
Having the implementation would be helpful. I haven't learned string hashing yet but it is on my TODO list.
It's like prefix sums where you find the sum of some segments in O(1) without checking the values. The approach is same for getting the substring hash, you don't need to check the characters itself.
So if you need L..R substring hash almost like in prefix sums you take R prefix and remove L — 1 prefix from it. There is an easy formula for it.