SPOJ PLD

Link : PLD

Category : Hashing

Hint : Consider substrings of S of length k and substrings of Reverse(S) of length k. If the hash value of one substring of S matches with hash value of substring of Reverse(S), and second starts when first ends, there is a match!

Solution : Well, the hint says pretty much all of it, except for a good hash function. For hash value of substring Si to Sj, we better not take O(k) time (else program is O(N*K) and gets TLE), hence I used the polynomial hash function

Hash({S_i to S_j})=(S_ia⁰+S_i+1a¹+S_i+2a²...)%p
Where a and p were primes (p was because of good hash spread, a was for no good reason :D ). This hash function allows Hash({S_i to S_j}) to be computed from Hash({S_i-1 to S_j-1}) in O(1) time, giving the complexity of hashing all substrings of S of length k O(N).

To do the index match (S's substring ends where Reverse(S)'s starts), keep a sorted vector at all hash values, and so a binary search.

Code:

	#include <iostream>
	#include <cstdio>
	#include <cstdlib>
	#include <cstring>
	#include <cmath>
	#include <algorithm>
	#include <vector>
	#include <list>
	#include <queue>
	#include <stack>
	#include <map>
	#include <set>
	#include <utility>
	#include <climits>
	#include <cfloat>
	#include <cassert>
	#define readint(n) scanf("%d",&n)
	#define readull(n) scanf("%llu",&n)
	#define readll(n) scanf("%lld",&n)
	#define readf(n) scanf("%f",&n)
	#define readd(n) scanf("%lf",&n)
	#define init(mem) memset(mem,0,sizeof(mem))
	#define ll long long int
	#define ull unsigned long long int
	using namespace std;
	#define HASHFAC 137
	#define MOD 1000003
	ll pow_log(ll base,ll exp){
	if(exp==0) return 1;
	else if(exp==1) return base;
	else if(exp%2==0){
	ll val=pow_log(base,exp/2);
	return (val*val)%MOD;
	}
	else{
	return (base*pow_log(base,exp-1))%MOD;
	}
	}
	bool binSearch(vector<int> *v,int val,int l,int h){
	if(h-l<=1){
	if((*v)[l]==val || (*v)[h]==val) return true;
	return false;
	}
	int m=(h+l)/2;
	if((*v)[m]==val) return true;
	else if((*v)[m]>val) return binSearch(v,val,l,m);
	return binSearch(v,val,m,h);
	}
	bool has(vector<int> *v,int val){
	if(v->size()==0 or (*v)[0]>val or (*v)[v->size()-1]<val) return false;
	return binSearch(v,val,0,v->size()-1);
	}
	int main(){
	int k,n;
	string str;
	readint(k);
	cin>>str;
	n=str.length();
	ll divfactor=pow_log(HASHFAC,MOD-2);
	ll multfactor=pow_log(HASHFAC,k-1);
	vector<int>* v=new vector<int>[MOD];
	// hash first k values
	ll hashval=0;
	ll fac=1;
	for(int i=0;i<k;i++){
	hashval=(hashval+fac*(str[i]-'a'))%MOD;
	fac=(fac*HASHFAC)%MOD;
	}
	v[hashval].push_back(k-1);
	#ifdef db
	cout<<hashval<<endl;
	#endif
	for(int i=k;i<n;i++){
	hashval=(hashval+MOD-(str[i-k]-'a'))%MOD;;
	hashval=(hashval*divfactor)%MOD;
	hashval=(hashval+(str[i]-'a')*multfactor)%MOD;
	v[hashval].push_back(i);
	#ifdef db
	cout<<hashval<<endl;
	#endif
	}
	int count=0;
	hashval=0;
	fac=1;
	for(int i=n-1;i>=n-k;i--){
	hashval=(hashval+fac*(str[i]-'a'))%MOD;
	fac=(fac*HASHFAC)%MOD;
	}
	if(has(&v[hashval],n-1)){
	count++;
	}
	for(int i=n-k-1;i>=0;i--){
	hashval=(hashval+MOD-(str[i+k]-'a'))%MOD;;
	hashval=(hashval*divfactor)%MOD;
	hashval=(hashval+(str[i]-'a')*multfactor)%MOD;
	if(has(&v[hashval],i+k-1)){
	count++;
	}
	}
	printf("%d\n",count);
	return 0;
	}

view raw pld.cpp hosted with ❤ by GitHub