Witam.
Mam za takie zadanie.
Podane N gdzie N to długość słowa, potem samo słowo, podają mi M jest to ilość zapytań. W każdym zapytaniu podają mi przedział o parzystej długości i pytają się czy jest to słowo podwójne np. bacbac , cc ,abab.
Przykład wejścia.
10
abbacbacca
5
1 4
3 8
5 8
8 9
1 10
poprawnym wynikiem jest:
NIE
TAK
NIE
TAK
NIE
Słowa występujące w kolejnych zapytaniach to: abba, bacbac, cbac, cc, abbacbacca.
Napisałem program który hashuje całe słowo od strony prefiksu (od lewej) i napisałem funkcje która porównuje słowa , jednakże jest problem. Program się wali kiedy long long obcina nam wartość hasha . Moze mi ktos pomoc ?
#include <iostream>
#include <math.h>
#define MX 1000005
using namespace std;
long long int w_hash[MX];
int X = 3;
int hash(int a, int b)
{
long long int wynik=ceil((w_hash[b]-w_hash[a-1])/pow(X,a));
return wynik;
}
int main()
{
int n;
cin>>n;
char * tab = new char [n];
for(int i = 0 ; i < n;i++)cin>>tab[i];
w_hash[0]=tab[0]-96;
for(int i = 1 ; i < n ; i++)w_hash[i]=w_hash[i-1]+((tab[i]-96)*pow(X,i));
int t;
cin>>t;
for(int i = 0 ; i < t;i++)
{
int a, b;
cin>>a>>b;
int zakres=ceil(a+(b-a+1)/2)-2;
//cout<<a-1<< " " <<zakres<< " " <<b-1<< " "<<hash(a-1,zakres)<< " "<<hash(zakres+1,b-1)<<endl;
if(hash(a-1,zakres)==hash(zakres+1,b-1))cout<<"TAK\n";
else cout<<"NIE\n";
}
return 0;
}
PS: nie bawiłem się jeszcze w preprocesnig potęgowy ani szybkie potęgowanie więc proszę o tym nie wspominać ;)