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
Divya Gupta: 2013-03-17 08:42:54

why always time limit exceeds..
& do i have to consider
input:
2
aammnnAA
output:
3
because string S is aammnn

Devashish Tyagi: 2012-11-29 05:56:58

lowercase letters mean it contains of english alphabets?

Hy Trường Sơn: 2011-02-02 12:20:45

I think that O(N*logN) algorithm will pass :D

madhav: 2010-09-27 06:37:17

does O(nlogn*logn) pass?

Priyanka Chatterjee: 2010-09-20 03:10:54

why am i getting internal error??

David Gómez: 2010-06-29 14:23:22

@Ishan: yes
@Praveen: yes
Input:
3
aaaa
Output:
2

Ishan: 2010-05-15 17:56:34

is O(n*k) algorithm supposed to give tle where n is the string length?

Last edit: 2010-05-15 17:57:29
Praveen Kumar: 2009-12-16 16:33:21

Are the palindromes which are lexicographically equal but starting from different positions considered as "DIFFERENT" palindromes ?

Karpovych Artem: 2009-07-01 06:25:58

How many test cases in this problem? Only one?


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