Pagini recente » Cod sursa (job #398145) | Cod sursa (job #1360852) | Cod sursa (job #1058225) | Cod sursa (job #2463846) | Cod sursa (job #2456075)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char s[1000005], t[2000005];
ll n, c, r, q[2000005], nr, ans;
int main()
{
fin >> s+1;
for(int i = 1; i <= strlen(s+1); i++)
{
t[nr] = '$';
nr++;
t[nr] = s[i];
nr++;
}
t[nr] = '$';
c = 1;
q[1] = 1;
r = 2;
ans = 1;
for(int i = 2; i <= nr; i++)
{
if(i<r)
q[i] = min(q[2*c-i], r-i);
ll a, b;
a = i-q[i];
b = i+q[i];
while(a-1>=0 && b+1<= nr && t[a-1] == t[b+1])
{
a--;
b++;
}
if(b > r)
{
r = b;
c = i;
}
q[i] = b-i;
ans += q[i]/2+q[i]%2;
}
fout << ans;
return 0;
}