Pagini recente » Cod sursa (job #808528) | Cod sursa (job #2905946) | Cod sursa (job #2076563) | Cod sursa (job #831383) | Cod sursa (job #1516618)
#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;
}