You are not logged in. Please login at to post your questions!


PALIPALI - Editorial






Let s be the given string, n is its length and s[i] denotes i-th symbol of s (0 <= i < n). Also we denote by s[i, j) the substring of s from i-th symbol inclusive to j-th symbol not inclusive. Compute for each i the so-called palindrome radius d[i]. Namely d[i] is the maximal number k such that the substring s[i - k, i + k) is a palindrome. This can be done by the elegant Manacher algorithm in O(n) time. Here you can read about it. Also you can use hashes and binary search to find this in O(n log n) time. So now assume that we find numbers d[i] (0 <= i < n). Obviously the substring s[i - k, i+3 * k) is beautiful if and only if j <= i + d[i] and d[j] >= 2 * (j - i) where j = i + k. (Since j <= i + d[i] then substring s[i - k, i + k) is a palindrome and since d[j] >= 2 * k then s[i - k, i+3 * k) is also a palindrome and has the form ttrttr where t = s[i - k, i)). So for each i the number of beautiful substrings of the form s[i - k, i+3 * k) is equal to number of those j <= i + d[i] such that 2 * j - d[j] <= 2 * i (and of course j > i). Let's sort all pairs (2 * j - d[j], j) by the usual lexicographical comparator. For each i from 0 to n-1 we at first add all new values of j such that 2 * j - d[j] <= 2 * i to some data structure T then delete i from T and then add to the answer the number of elements in T that are not greater than i + d[i]. Obviously when we are finding the last quantity, T contains only those values of j such that i < j (since we delete i at each step) and 2 * j - d[j] <= 2 * i. So the last quantity is number of beautiful substring of the form s[i - k, i+3 * k). What is T? We can use Cartesian tree or any balanced binary search tree that support order statistics as T. Also we can use segment tree for sum on the array of numbers from 0 to n-1. Then insertion (deleting) of the element is simply adding (subtraction) of one to (from) the corresponding element of the array and the number of needed beautiful substrings is the sum of values of the corresponding segment of the array. Finally you can use Fenwick tree instead of the segment tree (see author solution). So the overall complexity is O(n log n).


Can be found here.


Can be found here.

This question is marked "community wiki".

asked 26 Nov '12, 18:46

admin's gravatar image

0★admin ♦♦
accept rate: 36%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 26 Nov '12, 18:46

question was seen: 1,939 times

last updated: 26 Nov '12, 18:46