Mai intai trebuie sa te autentifici.

Cod sursa(job #1516615)

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

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

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

inline void build_sigma_power()
{
	pw1[0] = pw2[0] = 1;
	for(int i = 1; i< DIM; ++i)
	{
		//pw1[i] = (1LL * pw1[i-1] * sigma) % MOD1;
		pw2[i] = (1LL * pw2[i-1] * sigma) % MOD2;
	}
}
inline void build_Hash()
{
	for(int i = 1; i<= n; ++i)
	{
		//Hash1[i] = (Hash1[i-1] + 1LL * pw1[i]*(s[i] - 'a')) % MOD1;
		Hash2[i] = (Hash2[i-1] + 1LL * pw2[i]*(s[i] - 'a')) % MOD2;
	}
	for(int i = n; i; --i)
	{
		//rHash1[n-i+1] = (rHash1[n-i] + 1LL * pw1[n-i+1]*(s[i] - 'a')) % MOD1;
		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 H1 = (Hash1[p2] - Hash1[p1-1] + MOD1) % MOD1;
    int H2 = (Hash2[p2] - Hash2[p1-1] + MOD2) % MOD2;
    //int rH1 = (rHash1[p4] - rHash1[p3-1] + MOD1) % MOD1;
    int rH2 = (rHash2[p4] - rHash2[p3-1] + MOD2) % MOD2;
    if(p1 > p3)
    {
        //rH1 = (1LL * rH1 * pw1[p1 - p3]) % MOD1;
        rH2 = (1LL * rH2 * pw2[p1 - p3]) % MOD2;
    }
    if(p3 > p1)
    {
        //H1 = (1LL * H1 * pw1[p3 - p1]) % MOD1;
        H2 = (1LL * H2 * pw2[p3 - p1]) % MOD2;
    }
    if(/*H1 == rH1 && */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;
    //printf("%d %d %d\n", start, fin, step);
    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;
}