Pagini recente » Cod sursa (job #2633482) | Cod sursa (job #2488756) | Cod sursa (job #402354) | Cod sursa (job #791056) | Cod sursa (job #2385428)
#include<bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int n;
string s;
int L[2000002];
long long ans = 1;
int main()
{
f >> s;
n = s.size();
int N = 2*n + 1;
L[0] = 0;
L[1] = 1;
int C = 1, R = 2, i = 0, iMirror;
int maxLPSLength = 0, maxLPSCenterPosition = 0;
int diff = -1;
for (int i = 2; i < N; i++)
{
iMirror = 2*C-i;
L[i] = 0;
diff = R - i;
if(diff > 0)
L[i] = min(L[iMirror], diff);
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]++;
if (i + L[i] > R)
{
C = i;
R = i + L[i];
}
ans += (L[i] / 2) + (L[i] % 2);
}
g << ans << '\n';
return 0;
}