|
|
вернуться в форумUse Manacher's algo for comprehensive list of palindroms and try to calc 2 arrays: beg[i] - number of palindroms begins at position i, end[i] - number of palindroms ends at position i. after that ans = beg[i + 1] * end[i] for every i. To calc arrays you can use either O(n) offline (+=cnt at beg -= cnt after end; then sum) or efficient data structures. Edited by author 22.05.2017 20:40 |
|
|