Pagini recente » Borderou de evaluare (job #202007) | Cod sursa (job #2300182) | Cod sursa (job #327106) | Cod sursa (job #531707) | Cod sursa (job #2385455)
#include<bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
string s;
long long ans = 1;
int L[2000002], n, centru = 1, centruR = 2, dr, st, N;
int main()
{
f >> s;
n = s.size();
N = 2*n + 1;
L[1] = 1;
int mx = 0;
for (int i = 2; i < N; i++)
{
int st = 2 * centru - i;
if(centruR > i)
L[i] = min(L[st], centruR - i);
while (((i + L[i]) < N && i > L[i]) && ( ((i + L[i] + 1) % 2 == 0) || (s[(i + L[i] + 1)/2] == s[(i - L[i] - 1)/2])))
L[i]++;
ans += L[i] / 2 + (L[i] & 1);
if (i + L[i] > centruR)
{
centru = i;
centruR = i + L[i];
}
}
g << ans << '\n';
return 0;
}