# Competitive Programming: SPOJ – 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

Time limit: 0.100s

Link to problem

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 $O(n^2)$ solution. (An $O(n^2)$ 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();
}
}