Pagini recente » Cod sursa (job #1698305) | Cod sursa (job #1266217) | Cod sursa (job #1523198) | Cod sursa (job #1694681) | Cod sursa (job #2840663)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
using ll = long long;
const int NMAX = 1e6 + 1;
int N, M;
char A[NMAX], S[(NMAX << 1)];
int Z[(NMAX << 1)];
static inline void Read ()
{
f.tie(nullptr);
f >> (A + 1), N = (int)strlen(A + 1);
for(int i = 1; i < N; ++i)
S[++M] = A[i], S[++M] = '#';
S[++M] = A[N];
return;
}
static inline int my_min (int a, int b)
{
return ((a < b) ? a : b);
}
static inline void Solve ()
{
int L = 0, R = 0;
Z[1] = 1;
for(int i = 2; i <= M; ++i)
{
if(i <= R)
Z[i] = my_min(R - i + 1, Z[L + R - i]);
while(i - Z[i] >= 1 && i + Z[i] <= M && S[i - Z[i]] == S[i + Z[i]])
++Z[i];
if(i + Z[i] - 1 > R)
L = i - Z[i] + 1, R = i + Z[i] - 1;
else if(i + Z[i] - 1 == R && i - Z[i] + 1 > L)
L = i - Z[i] + 1;
}
return;
}
static inline void Find_Ans ()
{
ll ans = 2;
for(int i = 2; i < M; ++i)
ans += 1LL * ((Z[i] + (bool)(S[i] != '#')) >> 1);
g << ans << '\n';
return;
}
int main()
{
Read();
Solve();
Find_Ans();
return 0;
}