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 non-empty 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

Added by:Chinh Nguyen
Date:2008-02-07
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET

hide comments
2013-03-17 08:42:54 Divya Gupta
why always time limit exceeds..
& do i have to consider
input:
2
aammnnAA
output:
3
because string S is aammnn
2012-11-29 05:56:58 Devashish Tyagi
lowercase letters mean it contains of english alphabets?
2011-02-02 12:20:45 Hy Trường Sơn
I think that O(N*logN) algorithm will pass :D
2010-09-27 06:37:17 madhav
does O(nlogn*logn) pass?
2010-09-20 03:10:54 Priyanka Chatterjee
why am i getting internal error??
2010-06-29 14:23:22 David Gómez
@Ishan: yes
@Praveen: yes
Input:
3
aaaa
Output:
2
2010-05-15 17:56:34 Ishan
is O(n*k) algorithm supposed to give tle where n is the string length?

Last edit: 2010-05-15 17:57:29
2009-12-16 16:33:21 Praveen Kumar
Are the palindromes which are lexicographically equal but starting from different positions considered as "DIFFERENT" palindromes ?
2009-07-01 06:25:58 Karpovych Artem
How many test cases in this problem? Only one?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.