PLD-Palindromes

Palindromes

Given below code is for pld spoj or palindromes spoj.

Hint :- Simple implementation of Rolling Hash.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 15 September 2015 (Tuesday) 00:19
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000009
#define base 1223
ll prime[30009] , fh[30009] , bh[30009];
void prime_power(int n){
    prime[0] = 1;
    for(int i = 1 ; i <= n + 5 ; i++)
        prime[i] = (prime[i-1]*base)%mod;
}
void Hash(string &s , int n){
    for(int i = 1, j = n ; i<= n ;j--, i++){
        fh[i] = (fh[i-1] + s[i-1]*prime[i])%mod;
        bh[j] = (bh[j+1] + s[j-1]*prime[i])%mod;
    }
}
int count_palindromic_substring(string &s , int k){
    int n = s.size();
    int count = 0;
    int flag = 1;
    for(int i = k , j = 0 ,p_pow = n-k ; i<= n ;p_pow-=2 , j++,i++){
        ll hs1 , hs2;
        if(p_pow>=0){
            hs1 = (fh[i] - fh[j] + mod)%mod;
            hs1 = (hs1*prime[p_pow])%mod;
            hs2 = (bh[j+1] - bh[i+1] + mod)%mod;
        } else{
            hs2 = (bh[j+1] - bh[i+1] + mod)%mod;
            hs2 = (hs2*prime[abs(p_pow)])%mod;
            hs1 = (fh[i] - fh[j] + mod)%mod;
        }
        if(hs1 == hs2)
            count++;
    }
    return count;
}
int main(){
    
    string s ;
    int k;
    cin>>k>>s;
    prime_power(s.size());
    Hash(s , s.size());
    cout<<count_palindromic_substring(s , k)<<endl;
    return 0;
}