Cod sursa(job #1516618)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 3 noiembrie 2015 11:26:45
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

#define DIM 1000007
#define MOD2 666013
#define sigma 27

using namespace std;
char s[DIM];
int n, Hash2[DIM], pw2[DIM], rHash2[DIM], sum;

inline void build_sigma_power()
{
	pw2[0] = 1;
	for(int i = 1; i< DIM; ++i)
	{
		pw2[i] = (1LL * pw2[i-1] * sigma) % MOD2;
	}
}
inline void build_Hash()
{
	for(int i = 1; i<= n; ++i)
	{
		Hash2[i] = (Hash2[i-1] + 1LL * pw2[i]*(s[i] - 'a')) % MOD2;
	}
	for(int i = n; i; --i)
	{
		rHash2[n-i+1] = (rHash2[n-i] + 1LL * pw2[n-i+1]*(s[i] - 'a')) % MOD2;
	}
}
bool verificare(const int &p1, const int &p2, int p3, int p4)
{
    p3 = n - p3 + 1;
    p4 = n - p4 + 1;
    int H2 = (Hash2[p2] - Hash2[p1-1] + MOD2) % MOD2;
    int rH2 = (rHash2[p4] - rHash2[p3-1] + MOD2) % MOD2;
    if(p1 > p3)
    {
        rH2 = (1LL * rH2 * pw2[p1 - p3]) % MOD2;
    }
    if(p3 > p1)
    {
        H2 = (1LL * H2 * pw2[p3 - p1]) % MOD2;
    }
    if(H2 == rH2) return 1;
    return 0;
}
int check_middle(const int &key)
{
    int start = 0, fin = min(key - 1, n-key), step = 1;
    for(; step <= fin; step <<= 1);
    step >>= 1;
    for( ; step; step>>=1)
    {
        int index = start + step;
        if(index > fin) continue;
        if(verificare(key, key + index, key, key - index)) start = index;
    }
    return start + 1;
}
int check_left(const int &key)
{
    int start = 0, fin = min(key-1, n-key-1), step = 1;
    for(; step <= fin; step <<= 1);
    step >>= 1;
    for( ; step; step>>=1)
    {
        int index = start + step;
        if(index > fin) continue;
        if(verificare(key+1, key + index+1, key, key - index)) start = index;
    }
    return start + 1;
}


int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    scanf("%s", s+1);
    n = strlen(s+1);
    build_sigma_power();
    build_Hash();
    for(int i = 1; i<= n; ++i)
	{
		sum += check_middle(i);
		if(i == n) continue;
		if(s[i] == s[i+1]) sum += check_left(i);
	}
	printf("%d\n", sum);
	return 0;
}