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

×

BIGOF06-Editorial

Problem Link :

Contest
Practice

Author: Amrutansu Garanaik , Abhishek Patnaik
Tester: Keshow Sablaka, Amit Das
Editorialist: Amrutansu Garanaik , Amit Kumar Sahu

Difficulty :

easy-medium

Pre-requisite

manacher algorithm

Problem :

Given a string, print the number of substrings of it that are pallindromes.

Explanation

The problem is a direct application of manacher algorithm. This algorithm finds the length of pallindromic substring centered at every characters in the string. For example, consider the string aba. Manacher's algorithm converts the string to the form #a#b#a#. So length of longest pallindrome centered around a is 1, around b is 3 (aba), and around a is 1. Similarly, length of longest pallindrome around the # are also found (for even length pallindromes). Now, the number of pallindromic substring is the ceiling function of each length divided by 2.
See setter solution for implementation.


You can read about Manacher's algorithm here.

This question is marked "community wiki".

asked 05 May '15, 18:18

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

edited 09 May '15, 15:32

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×1,729
×14
×9
×2

question asked: 05 May '15, 18:18

question was seen: 508 times

last updated: 09 May '15, 15:32