Is it possible to get the length of biggest substring which is palindrome on a string on O(n)??
Is it possible to get the length of biggest substring which is palindrome on a string on O(n)??
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
There are two ways that I know of to solve this.
Use Manacher's Algorithm
Use Palindromic Tree
Hashes + 2 pointers
Can you explain how this will work?
We can use the idea similar to 2 pointers instead of binary search.
It will be O(N)
We will visit all centers, it's O(n). In every position we will try to update answer. All updates will work summary O(ans) = O(n), so algorithm's complexity is O(n).
I only know O(n log n) solution with hashes using binary search, how can it be done in O(n)?
If we change
for (int len = 0; len <= max_possible; i++)
in naive O(N^2) solution to
for (int len = ans; len <= max_possible; i++)
it will improove complexity to O(N)