Pagini recente » Cod sursa (job #3286898) | Cod sursa (job #1890517) | Cod sursa (job #1798627) | Cod sursa (job #1635993) | Cod sursa (job #2713552)
#include <bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
const int Max = 1e6 + 1;
void nos()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
char s[Max]="";
char sir[2*Max]="";
int n;
void read()
{
f>>s;
int i;
int it = -1;
for(i=0; s[i]; i++)
{
sir[++it] = '#';
sir[++it] = s[i];
}
sir[++it] = '#';
n = it;
}
int dp[2*Max];
void solve()
{
int left ;
int right = -1;
int i;
int last = n;
for(i=0; i<=n; i++)
{
int j;
if(right >= i)
j = min(dp[left + right - i],right - i + 1);
else
j = 1;
while(i - j >=0 and i+j <= last and sir[i-j] == sir[i+j])
++j;
dp[i] = j;
if(i+j - 1 > right)
{
right = i + j - 1;
left = i - j + 1;
}
}
int ans = 0;
// for(i=0; sir[i]; i++)
// cout<<sir[i]<<' ';
// cout<<'\n';
// for(i=0; sir[i]; i++)
// cout<<dp[i]<<' ';
// cout<<'\n';
for(i=0; i<=n; i++)
ans+= dp[i] / 2;
g<<ans;
}
void restart()
{
}
int32_t main()
{
nos();
read();
solve();
restart();
return 0;
}