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 abababOutput:2

Time limit: 0.100s

Solution below . . .

### Solution

Some of the comments on the problem page are from people who claim to have succeeded with a “brute force” approach, including one comedian who claimed an solution. (An algorithm is obviously not going to run on a 30,000-character string in 0.1 seconds.)

I tried a brute force approach — reversing the string and comparing k characters at a time to the original — and got a TLE (time limit exceeded).

Instead of comparing k characters at a time, we can implement a rolling hash, which allows us to add and subtract one character at a time. (The link is in Russian, but the Google translation is good.)

As the hash values quickly get very large, the link recommends letting them overflow a long (64-bit) integer, as if taking a hash modulo 2 ^ 64. That might work but I’d rather computer the mod explicitly.

import java.util.Scanner; class Main { static final long mod = 1000000009; static final int base = 31; static long prime[] = new long[30009]; static long forwardHash[] = new long[30009]; static long backwardHash[] = new long[30009]; static void primePower(int n) { prime[0] = 1; for (int i = 1; i <= n + 5; i++) prime[i] = (prime[i - 1] * base) % mod; } static void createHash(String s, int n) { for (int i = 1, j = n; i <= n; j--, i++) { forwardHash[i] = (forwardHash[i - 1] + s.charAt(i - 1) * prime[i]) % mod; backwardHash[j] = (backwardHash[j + 1] + s.charAt(j - 1) * prime[i]) % mod; } } static int countPalindromicSubstrings(String s, int k, int n) { int count = 0; for (int i = k, j = 0, pPow = n - k; i <= n; pPow -= 2, j++, i++) { long hash1, hash2; if (pPow >= 0) { hash1 = (forwardHash[i] - forwardHash[j] + mod) % mod; hash1 = (hash1 * prime[pPow]) % mod; hash2 = (backwardHash[j + 1] - backwardHash[i + 1] + mod) % mod; } else { hash2 = (backwardHash[j + 1] - backwardHash[i + 1] + mod) % mod; hash2 = (hash2 * prime[Math.abs(pPow)]) % mod; hash1 = (forwardHash[i] - forwardHash[j] + mod) % mod; } if (hash1 == hash2) count++; } return count; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int k = sc.nextInt(); String s = sc.next(); int n = s.length(); primePower(n); createHash(s, n); System.out.println(countPalindromicSubstrings(s, k, n)); sc.close(); } }