Problem Link :Author: Amrutansu Garanaik , Abhishek Patnaik Difficulty :easymedium Prerequisitemanacher algorithmProblem :Given a string, print the number of substrings of it that are pallindromes.ExplanationThe 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.
This question is marked "community wiki".
asked 05 May '15, 18:18
