PLD - Palindromes

no tags 

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

hide comments
avik26091998: 2017-12-24 07:22:01

O(n*n) accepted!!!

vengatesh15: 2017-03-04 14:19:19

Brute force pass..

ashishranjan28: 2017-01-05 16:43:49

brute force :)

minhthai: 2016-03-11 12:12:08

try hashing if tle

Anik Dasgupta: 2015-08-15 17:07:35

i am getting an error in the 9th case. please help!

Scape: 2015-07-25 18:06:12

Can be solved in O(N).

jose: 2014-11-05 22:48:31

which is the case 6 or 7

Fahim Zubayer: 2013-05-07 15:02:39

Guess what? O(N log(N)^2) works!
It is rather slow,though.

Divya Gupta: 2013-03-25 08:37:28

gives tle

Divya Gupta: 2013-03-17 09:34:53

time limit eceeds


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