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();
  }
}