Hi guys, I need your help in this problem. it is problem 'K' (subpalindroms) in this contest http://www.codeforces.com/gym/100032/attachments. in the problem a string S with length < 10^5 is given and want us to answer m <3*10^5 queries, each query want us to count the number of palindromic substrings in a given interval. I couldn't find any solution better than O(n^2) although I tried to use hashing and palindromic tree any hint please .. thanks in advance.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3845 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3630 |
| 4 | orzdevinwang | 3573 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | jqdai0815 | 3532 |
| 8 | ecnerwala | 3501 |
| 9 | gyh20 | 3447 |
| 10 | Rebelz | 3409 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | adamant | 163 |
| 3 | awoo | 161 |
| 4 | nor | 152 |
| 5 | maroonrk | 151 |
| 5 | -is-this-fft- | 151 |
| 7 | TheScrasse | 148 |
| 8 | atcoder_official | 146 |
| 9 | Petr | 145 |
| 10 | pajenegod | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.06.2024 08:01:16 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by AzorAhai (previous revision, new revision, compare).
I think this can be solved with Suffix Automata. A similar problem where you have to count substrings of any kind can be solved using this. Not sure about palindromic substring counting though.
You can modify Manacher's algorithm + DP ,and solve it in O(N). I don't know how this works but here you go :
If you only need a hint, don't open this link! http://stackoverflow.com/questions/19801081/find-all-substrings-that-are-palindromes
thanks MedoN11 but the solution in the link solve the problem of counting palindromic substrings in the whole string but my problem is how to count them efficiently in some given range .. do you have an idea how to do so
you could do manacher to get the palindromes and then do mo's algorithm on queries, it will be
How would I updadte the count when extending/shrinking the current intervall?