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