PLD  Palindromes
A palindrome is a word, phrase, number or other sequence of units that has the property of reading the same in either direction, e.g. 'racecar', 'solos'.
Task
You are given a number k (2≤k≤30000) and a nonempty string S whose length does not exceed 30000 lowercase letters.
We say two palindromes are different when they start from different positions. How many different palindromes of the length k does S contains?
Input
The first line contains K. The second line contains S. K does not exceed the length of S.
Output
The first and only line should consist of a single number  the number of palindromes found.
Example
Input: 5 ababab Output: 2
hide comments
Divya Gupta:
20130317 08:42:54
why always time limit exceeds..


Devashish Tyagi:
20121129 05:56:58
lowercase letters mean it contains of english alphabets? 

Hy Trường Sơn:
20110202 12:20:45
I think that O(N*logN) algorithm will pass :D 

madhav:
20100927 06:37:17
does O(nlogn*logn) pass? 

Priyanka Chatterjee:
20100920 03:10:54
why am i getting internal error?? 

David Gómez:
20100629 14:23:22
@Ishan: yes


Ishan:
20100515 17:56:34
is O(n*k) algorithm supposed to give tle where n is the string length? Last edit: 20100515 17:57:29 

Praveen Kumar:
20091216 16:33:21
Are the palindromes which are lexicographically equal but starting from different positions considered as "DIFFERENT" palindromes ? 

Karpovych Artem:
20090701 06:25:58
How many test cases in this problem? Only one? 
Added by:  Chinh Nguyen 
Date:  20080207 
Time limit:  0.100s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 